原题

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]]

解题思路

递归：递归的方法，创建一个visit判断此值是否已经添加过，每一层不断地循环，加入没有被访问的元素，直到最后结果的长度满足要求加入答案中

class Solution(object):    def permute(self, nums):        """        :type nums: List[int]        :rtype: List[List[int]]        """        if nums == None:            return []        visit = [0 for i in range(len(nums))]        self.ret = []        self._permute(nums, visit, 0, [])        return self.ret            def _permute(self, nums, visit, count, ret):        if count == len(nums):            self.ret.append(ret)            return        for i in xrange(len(nums)):            if visit[i] == 0:                # ret += [nums[i]]  容易出错，如果加入这句后面需要还原，不然影响后面的循环                visit[i] = 1                self._permute(nums, visit, count+1, ret+[nums[i]])                visit[i] = 0

非递归：跟之前求subsets的思路类似（不过这个是求重复项，sbusets是求非重复），也是从一个个元素一层层加上去，只不过加入结果的时候必须满足长度要求

class Solution(object):    def permute(self, nums):        """        :type nums: List[int]        :rtype: List[List[int]]        """        if nums is None:            return []        result = []        self.helper(nums, [], result)        return result    def helper(self, List, path, result):        if len(path) == len(List):            result.append(path)            return                # 跟subsets思路差不多，不过这个是重复，sbusets是非重复        # 也是从一个个元素一层层加上去，只不过加入结果的时候必须满足长度要求        for i in range(len(List)):            # 不重复加入同一元素            if List[i] in path:                continue            # path.append(List[i])            self.helper(List, path + [List[i]], result)            # path.pop()