6
\$\begingroup\$
  1. Given an array of unique numbers find the combinations
  2. Doing a deep copy in the code to avoid changes to the passed obj by reference
  3. This has a run time of \$O(n \times \text{#ofcombinations})\$ - can this be done better -- iteratively and easy to understand
import copy
def gen_combinations(arr): # 
    res = [[]]
    for ele in arr:
        temp_res = []
        for combination in res:
            temp_res.append(combination)
            new_combination = copy.copy(combination)
            new_combination.append(ele)
            temp_res.append(new_combination)
            res = copy.copy(temp_res)
        
    return res
New contributor
Juggernaut17 is a new contributor to this site. Take care in asking for clarification, commenting, and answering. Check out our Code of Conduct.
\$\endgroup\$
10
\$\begingroup\$

First, a side note. What you call combination is usually called subset.

In a set of \$n\$ elements an average length of a subset is \$\dfrac{n}{2}\$. That is, generating a single subset takes \$O(n)\$ time. You cannot get a time complexity better than \$O(n2^n)\$.

The space complexity is a different matter. If you indeed need all the subset at the same time, then again the space complexity cannot be better than \$O(n2^n)\$. On the other hand, if you want one subset at a time, consider converting your function to a generator, which would yield subsets one at a time.

A more or less canonical way of generating subsets uses the 1:1 mapping of subsets and numbers. Each number a in the \$[0, 2^n)\$ range uniquely identifies subset of \$n\$ elements (and vice versa). Just pick the elements at the position where a has a bit set.

All that said, consider

def generate_subsets(arr):
    n = len(arr)
    for a in range(2 ** n):
        yield [arr[i] for i in range(n) if (a & (1 << i)) != 0]
\$\endgroup\$
1
  • 1
    \$\begingroup\$ Just a note, one can always iterate a finite generator and fill an array with all the results. So it actually feels more flexible to do that way even if now, you need them all at once. \$\endgroup\$ – slepic 2 days ago

Your Answer

Juggernaut17 is a new contributor. Be nice, and check out our Code of Conduct.

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.