Recursively find all combinations of list

Question

Problem statement

I want to get all possible combinations out of my list (including the empty list).

My code so far is:

def combination(l):
    result = []
    for item in range(len(l)):
        cut_list = l[:item] + l[item + 1:]
        if len(cut_list) > 1:
            combination(cut_list)
        elif len(cut_list) == 1:
            result += cut_list
    return result


print(combination([1, 2, 3]))

My output is an empty List

[]

i want this Output:

[[], [1], [2], [3], [1, 2], [1, 3], [2, 3], [1, 2, 3]]

I am pretty sure something with my return is not right.

Any help is extremely appreciated.

Answer 1

A recurrence relation can be found this way: "A combination of list l either uses the last element of l, or it doesn't."

So we find recursively the combinations of sublist l[:-1] (the sublist containing all elements except the last one); and then we either add or don't add the last element.

Recursive version

This recursion needs a base case. The base case is: if the list is empty, then the only combination is the empty combination.

def combinations(l):
    if l:
      result = combinations(l[:-1])
      return result + [c + [l[-1]] for c in result]
    else:
      return [[]]

print(combinations([1,2,3]))
# [[], [1], [2], [1, 2], [3], [1, 3], [2, 3], [1, 2, 3]]

Iterative version

Just because we have a recurrence relation doesn't mean we need recursion; for-loops work very well to apply recurrence relations repeatedly.

def combinations(l):
  result = [[]]
  for x in l:
    result = result + [c + [x] for c in result]
  return result

print(combinations([1,2,3]))
# [[], [1], [2], [1, 2], [3], [1, 3], [2, 3], [1, 2, 3]]