Permutations

题目描述

Given a collection of numbers, return all possible permutations.

解题方法

因为没有non-descending这种限制，所以之前的数其实也可以用，所以不需要Index来track。 为了避免同一个数被重复用，用另一个userarray来保存用过的index。

permutations的不同顺序是不同permutations

Solution

class Solution(object):
    def permute(self, nums):
        """
        :type nums: List[int]
        :rtype: List[List[int]]
        """
        results = []
        if not nums:
            return results
        length = len(nums)
        nums.sort() #not necessary in this question, but good habit
        used = [False for i in range(length)]
        self.permuteHelper(nums, used, results, [])
        return results

    def permuteHelper(self, nums, used, results, curList):
        if len(curList) == len(nums):
            tmpList = list(curList)
            results.append(tmpList)

        for i in range(len(nums)):
            if not used[i]:
                curList.append(nums[i])
                used[i] = True
                self.permuteHelper(nums, used, results, curList)
                curList.pop()
                used[i] = False

Reference