Permutations

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

终于开始做回溯的题目了，其实这是一道枚举的题目.思路是DFS，每次找到长度为需要长度的序列则算dfs结束，然后进行回溯。需要列举出所有排列的情况，时间复杂度是Ｏ(n!*n)．因为一共有n！种结果，每个结果的处理事件为O(n)。所以最终的时间复杂度为O(n!*n).

回溯方法常见的是采用递归来做，对于每次选择都是深入一个递归函数，如果已经找到可行解或者当前条件不符合，则退出，并回到开始进入该递归子函数之前的状态，俗称保护现场(回溯）．另外这题permutation中，已做过的选择不能再选择，所以可以保存一个used数组来确定是否有用过这个这个数字，用过则跳过．代码如下：

class Solution(object):
    def permute(self, nums):
        """
        :type nums: List[int]
        :rtype: List[List[int]]
        """
        if not nums:
            return [[]]
        allPer = []
        used = [False] * len(nums)　＃用于记录该数字是否被用过
        per = []
        self.helper(nums, used, per, allPer)
        return allPer
    def helper(self,nums, used, per, allPer):
        if len(per) == len(nums):
            allPer.append(per+[])
            return 
        for i in xrange(len(nums)):
            if used[i]: continue
            used[i] = True
            per.append(nums[i])
            self.helper(nums, used, per, allPer)
            used[i] = False　＃返回原状态，保护现场
            per.pop()　　　　　＃返回原状态，保护现场

以上回溯的做法，其实也是每一步做出选择，之后该选择上再做出选择的过程．其实相当于先选出第一个数字，之后在一个数字的组合中，加入第二个数字．．．对于[1,2,3]举例如下：

当只有1时候：[1]
当加入2以后：[2, 1], [1, 2]
当加入3以后：[3, 2, 1], [2, 3, 1], [2, 1, 3], [3, 1, 2], [1, 3, 2], [1, 2, 3]

这种做法的代码如下：

class Solution(object):
    def permute(self, nums):
        """
        :type nums: List[int]
        :rtype: List[List[int]]
        """
        res = [[]]
        for i in xrange(len(nums)):
            new_res = []
            for per in res:
                for j in xrange(i+1):
                    new_res.append(per[0:j]+[nums[i]]+per[j:])　＃注意必须选择的是放入new_res的结果需要是深copy,防止后续修改．
            res = new_res
        return res