Permutations

Question

Given a list of numbers, return all possible permutations.

Example For nums = [1,2,3], the permutations are:

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

Challenge Do it without recursion.

Thoughts

注意点

• 用一个hashmap存已经用过的char

Solution

class Solution:
    """
    @param nums: A list of Integers.
    @return: A list of permutations.
    """
    def permute(self, nums):
        # write your code here
        if not nums:
            return []
        self.resultList = []
        self.usedNum = {}
        self.nums = nums
        self.length = len(nums)
        self.permuteHelper([])
        return self.resultList

    def permuteHelper(self, curList):
        if len(curList) == self.length:
            newList = list(curList)
            self.resultList.append(newList)

        for i in self.nums:
            if i in self.usedNum and self.usedNum[i] == True:
                continue
            else:
                curList.append(i)
                self.usedNum[i] = True
                self.permuteHelper(curList)
                curList.pop()
                self.usedNum[i] = False