How do I return Combinations using recursion in Python

Question

I want to print the combinations of all the elements of a list. But every time my codes results in a list of empty lists. What is want is input = [1,2,3] Output = [[3],[1],[2],[1,2,3],[1,3],[2,3],[1,2],[]] What I am getting is [[][][][][][][][]]

My Python code

class Solution:
def subsets(self, nums: List[int]) -> List[List[int]]:
    result = []
    curNums = []
    def dfs(nums , i):
        if i == len(nums):
            result.append(curNums)
        else:
            curNums.append(nums[i])
            dfs(nums , i+1)
            curNums.pop()
            dfs(nums , i+1)
    dfs(nums , 0)
    return result

Refer to this answer: https://stackoverflow.com/a/464882/8350440 — Ji Wei, Apr 16 '20 at 07:21
In this case we need to use the `powerset` recipe from [`itertools`](https://docs.python.org/3/library/itertools.html#itertools-recipes) — Matthias, Apr 16 '20 at 07:38

score 0 · Accepted Answer · answered Apr 16 '20 at 07:36

The curNums list you are appending is the same list every time - so the append/pop are all being made on the same list.

Instead what you need to append to the result should be a new copy of the list every time - try result.append(curNums[:]). Creating a copy of the current list values.

score 0 · Answer 2 · answered Apr 16 '20 at 07:45

Why not use https://docs.python.org/2/library/itertools.html#itertools.permutations and create a permutation of each subset length? Something like this:

import itertools  
input =  [1,2,3]
results = []
for i in range(len(input)+1):
    results.append(list(itertools.permutations(input,i)))

How do I return Combinations using recursion in Python

2 Answers2