# Generate combinations of a given sequence without recursion

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:
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

• Step 2 says "Doing a deep copy...", but copy.copy() does a shallow copy, which is fine in this case. – RootTwo May 8 at 16:35
• thanks for catching that @RootTwo, edited the description – 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]

• 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. – slepic May 4 at 10:41