Store Subsequences in list of lists using recursion in python

Question

This may sound very simple, I tried searching for the solution but couldn't find it hence posting the question. Appreciate the help, Thanks in advance.

I am trying to print all the subsequences of a given list/string in python using recursion. Below is the output I expect:

Given Input list : [1,3,2] Output List : [[],[1],[3],[2],[1,2],[1,3],[3,2],[1,3,2]]

This is what I have tried:

def printSubsequences(ind,ans,l,n):
    final_ans = []
    if ind == n:
        return ans
    else:
        ans.append(l[ind])
        final_ans.extend(printSubsequences(ind+1,ans,l,n))
        
        ans.pop()
        
        final_ans.extend(printSubsequences(ind+1,ans,l,n))
        return final_ans
       
print(printSubsequences(0,[],[1,3,2],3))

Output of above code: [1, 3, 2, 1, 3, 1, 2, 1, 3, 2, 3, 2]

The output is correct partially as It does not contain [] (empty subset), but I want it in specified format as aforementioned. I also tried append method but that is giving Output : [[[[], []], [[], []]], [[[], []], [[], []]]].

I don't understand what I am doing wrong here, Can someone explain - Why append is failing and extend is working, and How can I get my desired output ?

Answer 1

You have run into this classic python trap:

• List of lists changes reflected across sublists unexpectedly

When you append ans to the list of results, it's always a reference to the same list ans, not a copy. So when you call ans.pop(), you erase the last element of that list, and it is removed in all subsequences. Try for instance this code:

a = [2]
b = [a, a, a]
print(b) # [[2], [2], [2]]
a.pop()
print(b) # [[], [], []]

The workaround is to adopt a more functional style, never modifying the ans list in-place, and rather building a new list when needed for the recursive calls:

def subsequences(ind,ans,l,n):
    final_ans = []
    if ind == n:
        return [ans]
    else:
        final_ans.extend(subsequences(ind+1,ans + [l[ind]],l,n))
        final_ans.extend(subsequences(ind+1,ans,l,n))
        return final_ans

>>> subsequences(0, [], [1,2,3], 3)
[[1, 2, 3], [1, 2], [1, 3], [1], [2, 3], [2], [3], []]

Notable modifications:

• I renamed the function subsequences rather than printSubsequences, since it doesn't print;
• I fixed the base case which should be return [ans], not return ans;
• I replaced the calls to ans.append and ans.pop with + in the recursive calls.