moonlightshadow123
6/25/2017 - 9:25 AM

46. Permutations

  1. Permutations
class Solution(object):
    def permute(self, nums):
        """
        :type nums: List[int]
        :rtype: List[List[int]]
        """
        self.nums = nums
        self.res = []
        self.cur = []
        self.isVisited = [0] * len(nums)
        self.backtracking()
        return self.res
    def backtracking(self):
        if len(self.cur) == len(self.nums):
            self.res.append([each for each in self.cur])
            return
        for i in range(len(self.nums)):
            if self.isVisited[i] == False:
                # Update both self.isVisited and self.cur
                self.isVisited[i] = True
                curNum = self.nums[i]
                self.cur.append(curNum)
                self.backtracking()
                del self.cur[-1]
                self.isVisited[i] = False

https://leetcode.com/problems/permutations/#/description

Given a collection of distinct numbers, return all possible permutations.

For example, [1,2,3] have the following permutations:

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