1

I'm using backtracking to get permutations of non-duplicates nums list. E.g nums = [1, 2, 3], the output should be '[[1,2,3],[1,3,2],[2,1,3],[2,3,1],[3,1,2],[3,2,1]]. I'm stuck on pop elements out from recursively stack. Anyone can help me what's the problem of my code. Thanks.

class Solution(object):
    def permute(self, nums):
        visited = [False] * len(nums)
        results = []
        for i in range(len(nums)):
            temp = []
            if not visited[i]:
                temp.append(nums[i])
                self._helper(nums, i, visited, results, temp)
        return results

    def _helper(self, nums, i, visited, results, temp):
        visited[i] = True
        if all(visited):
            results.append(temp)
        for j in range(len(nums)):
            if not visited[j]:
                temp.append(nums[j])
                self._helper(nums, j, visited, results, temp)
                temp.pop()
        visited[i] = False

nums = [1, 2, 3]
a = Solution()
print(a.permute(nums))

And I got [[1], [1], [2], [2], [3], [3]].

Jonathon.lau
  • 43
  • 5
  • Welcome to StackOverflow. Please read and follow the posting guidelines in the help documentation. [Minimal, complete, verifiable example](http://stackoverflow.com/help/mcve) applies here. We cannot effectively help you until you post your MCVE code and accurately describe the problem. We should be able to paste your posted code into a text file and reproduce the problem you described. "I'm stuck on pop elements out [sic]" is not a problem specification. Also, your posted code fails to run at all, since you failed to include all the dependencies. – Prune Jan 30 '18 at 16:17

1 Answers1

0

Your code is logically right. All what you need it's to use copy.

Why it so - please check this answer on SO.

import copy


class Solution(object):
    def permute(self, nums):
        visited = [False] * len(nums)
        results = []
        for i in range(len(nums)):
            temp = []
            if not visited[i]:
                temp.append(nums[i])
                self._helper(nums, i, visited, results, temp)
        return results

    def _helper(self, nums, i, visited, results, temp):
        visited[i] = True
        if all(visited):
            results.append(copy.copy(temp))
        for j in range(len(nums)):
            if not visited[j]:
                temp.append(nums[j])
                self._helper(nums, j, visited, results, temp)
                temp.pop()
        visited[i] = False


nums = [1, 2, 3]
a = Solution()
print(a.permute(nums))

# [[1, 2, 3], [1, 3, 2], [2, 1, 3], [2, 3, 1], [3, 1, 2], [3, 2, 1]]
chinskiy
  • 2,557
  • 4
  • 21
  • 40