1. Given an array of unique numbers find the combinations
  2. Doing a shallow 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:
            new_combination = copy.copy(combination)
            res = copy.copy(temp_res)
    return res
  • \$\begingroup\$ Step 2 says "Doing a deep copy...", but copy.copy() does a shallow copy, which is fine in this case. \$\endgroup\$ – RootTwo May 8 at 16:35
  • \$\begingroup\$ thanks for catching that @RootTwo, edited the description \$\endgroup\$ – Juggernaut17 May 8 at 21:06

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]
  • 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 May 4 at 10:41

Your Answer

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.