Why does this string permutation code exceed the recursion limit?

Question

I wrote a python program to give all the permutations of a string, using backtracking:

class Solution(object):
    def permute(self, nums):
        """
        :type nums: List[int]
        :rtype: List[List[int]]
        """
        if nums == None or len(nums) <= 1:
            return [nums]

        res_lst = []
        res = []
        self.permuteHelper(res_lst, nums, res)
        return res_lst

    def permuteHelper(self, res_lst, nums, res):
        if len(res) == len(nums):
            res_lst.append(res)
            return

        for n in nums:
            if n not in res:
                self.permuteHelper(res_lst, nums,res+[n])
                res = res[:-1] #Prune back one node

This one always exceeds the maximum recursion limit. Since at each recursion step I pass result list + [n] to the next recursion call, I suppose it will finally reach the end case len(res) == len(nums).

Doe anybody have idea why that does not happen?

Answer 1

Ah, that was subtle. Remove the line:

 res = res[:-1] #Prune back one node

And it works. You remove one digit from the given permutation, which means that for each time you do that, you add one recursion level to the recursion, so you keep having to go deeper and deeper.

Also it messes up the permutations completely.