What is the time complexity of the following algorithm and is there any optimization I can do?

Below is a memoized recursion-based solution. It is still exponential time, and its runtime scales with the values in the array, but I figure it can provide a known-good baseline for other solutions.

from math import comb, factorial
from collections import Counter

def find_max_partitions(arr):
    counter = Counter(arr)
    
    num_zeros = counter[0]
    counter[0] = 0

    num_signed_pairs = 0
    for x in list(counter):
        count = min(counter[x], counter[-x])
        counter[ x] -= count
        counter[-x] -= count
        num_signed_pairs += count

    arr = [x for x, c in counter.items() for _ in range(c)]
    
    k = 1
    while (count := count_valid_partitions(arr, k)) > 0:
        k += 1
    return k - 1 + num_zeros + num_signed_pairs

def count_valid_partitions(arr, k):
    if k == 1:
        return 1 if arr and sum(arr) == 0 else 0
        
    arr = list(arr)
    sums = [0] * k
    
    count = _count_valid_partitions(arr, k, sums, {})
    
    count -= sum(count_valid_partitions(arr, i) * comb(k, i) * factorial(i) for i in range(1, k))
    count //= factorial(k)
    return count
        
def _count_valid_partitions(arr, k, sums, memo):
    if not arr:
        return 1 if not any(sums) else 0
        
    elem = arr.pop()

    count = 0
    for idx in range(k):
        sums[idx] += elem
        
        key = tuple(sorted(sums)), len(arr)
        val = memo.get(key)
        if val is None:
            val = memo[key] = _count_valid_partitions(arr, k, sums, memo)
        count += val
        
        sums[idx] -= elem
    
    arr.append(elem)
    return count

Let N be the size of your input array, A be the sum of the negative values, B be the sum of the positive values, and P be the maximum number of partitions (our output), the time complexity will be O(N*(B-A)^(P+1)).

I've already implemented a few optimizations like stripping off zeros and signed pairs, making these into partitions of their own, and sorting the intermediate sums to avoid a P! duplication of effort. There are still a number of optimizations that could be made, but most of them will have little to no effect on performance. We could cache the result of smaller k-value calls to count_valid_partitions (negligible overall), early-exit the count once its known to exceed some required threshold (also negligible savings), or stuff like avoiding creating new N-tuples at every step. Overall, these won't change the time complexity.

There is one more major optimization that could be made to this approach however. Take the remaining items, work out the 3SUM solutions, and take the largest set of independent 3-tuples from those. There exists a maximal partitioning where all of these independent 3-tuples are either (a) each their own standalone partition or (b) are scattered into distinct partitions (no two elements of the same tuple being assigned to the same partition). This can significantly reduce the search space, leading to large performance gains (still the same time complexity however). Even for the case of just one tuple, the search space is cut in third.

There is still potential to do better though. Offhand, I have an idea for a potential O(N*(B-A)^(P/2)) solution, however its drastically more complex, has larger overhead / hidden constants, and probably won't be feasible. Additionally, you could go for a O(P^(N/2)) time meet-in-the-middle solution. The naive implementation would have an equal space complexity O(P^(N/2)), but there are efficient time-memory tradeoffs you can make to lower the space complexity by more than you increase the time complexity by (such as decreasing memory by a factor of M and increasing time by sqrt(M)).

Your problem contains the 3-Partition Problem as almost a special case. Namely, can we partition a set into sets of 3 that each have the same sum. That is strongly NP-complete. Meaning that not only is it NP-complete, but there is no pseudo-polynomial approximation. So you should not expect better than an exponential worst case.

I did not walk through your complexity analysis, but the end result sounds reasonable.

Now can we be faster? In worst cases? No. In practice? Let's pull out my old cheat sheet.

• A* Search
• Subset sum pseudo-polynomial approximation.
• My personal "turn dynamic programming into explicit solutions" trick. Only personal because nobody seems interested in learning how to do it for themselves.

So here's an outline of how I would do it.

1. Sort the elements in decreasing absolute value, then increasing value.
2. Separate the 0s out.
3. Turn that into tuples (abs(element), count_negatives, count_positives).
4. Create a naive upper bound for A* search. (Based on pair negs with pos, hope that all else turns into as many groups of 3 as possible.)
5. Do an A* search for the best division.

So for your example there are no 0s. After sorting we get [5, -4, 4, -3, -2]. The naive lower bound will be 2 (we can pair -4, 4, and divide the remaining 3). The A* search will immediately verify that this works.

Unfortunately there are two problems:

1. That A* search really needs persistent data structures to code efficiently, and nobody has a good Python library for that. Why does it need that? It's because it allows you to very cheaply say, "Take this element here, and that element there out of this long list" without having to use a lot of memory on the modified copy of the array.
2. I've done too many by hand "dynamic programming to explicit solutions" and want to write a library for it next. That lets us take a first element and find all of its solutions of lengths 2, 3, 4, etc. And then try those solutions in lexicographic order. Which, oh geez, we repeat to try to find a good solution for the next one. And so on.

I'm in the process of writing both libraries, but they are medium large projects, so no promise on when they will be done.

But that should give an idea of how much this could be optimized.