Python - List Variable Not Storing Proper Result In Recursion

I am trying to store all possible parenthesisation of a list through recursion. Example: printRange(0,3) Answer will be [[0],[1], [2]], [[0], [1, 2]], [[0, 1], [2]], [[0, 1, 2]] I

Solution 1:

This is happening because cans is a list of lists, and those inner lists get mutated. You need to append a deep copy of cans to res, i.e. a copy that makes copies of the internal lists. You can do that with deepcopy from the copy module, or just write a simple deepcopy that works for a list of lists.

Here's a repaired version of your code.

#from copy import deepcopy

def deepcopy(list2d):
    return [u[:] for u in list2d]

res = []
def printRange(st, size, cans=[]):
    if(st == size):
        res.append(deepcopy(cans))
        print cans

    l = []
    for i in range(st, size):
        l.append(i)
        tmp = [] + cans
        tmp.append(l)
        printRange(i+1, size, tmp)

printRange(0, 4)
print res

output

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

---

Note that it's generally not a good idea to use a list or other mutable object as a default argument because default arguments are assigned when the function is defined, not when it's called, and that can cause surprising behaviour. It doesn't actually cause problems for your code, but it's still a good idea to avoid default mutable args unless you need that "interesting" behaviour, eg so it can be used as a memoization cache, and even then you should use a comment explaining that you're doing it on purpose. :) See “Least Astonishment” and the Mutable Default Argument for further details.

---

I would approach this task in a slightly different way, with one of my favourite "toys": a recursive generator.

def brackets(n):
    if n == 0:
        yield [[0]]
    else:
        for seq in brackets(n - 1):
            yield seq + [[n]]
            yield seq[:-1] + [seq[-1] + [n]]

for seq in brackets(3):
    print seq

output

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

If you do actually want a list containing all the results, just pass the generator to the list constructor:

res = list(brackets(2))
print res

output

[[[0], [1], [2]], [[0], [1, 2]], [[0, 1], [2]], [[0, 1, 2]]]