[Backtracking]46. Permutations

• 分类：Backtracking
• 时间复杂度: O(n)

46. Permutations

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

Example:

Input: [1,2,3]
Output:
[
  [1,2,3],
  [1,3,2],
  [2,1,3],
  [2,3,1],
  [3,1,2],
  [3,2,1]
]

代码：

方法:

class Solution:
    def permute(self, nums):
        """
        :type nums: List[int]
        :rtype: List[List[int]]
        """
        res=[]
        if nums==None or len(nums)==0:
            return res
        list_=[]
        self.helper(res,list_,nums)
        return res
    
    def helper(self,res,list_, remains):
        if remains==[]:
            res.append(list_.copy())
        for i in range(len(remains)):
            list_.append(remains[i])
            used_num=remains[i]
            remains.remove(used_num)
            self.helper(res,list_, remains)
            remains.insert(i,used_num)
            list_.pop()

讨论：

1.和combination那两道的方法非常的像，我就自己先做了一遍，再看看别人的代码就做好了（非常棒）！！！鼓励自己！

2. 注意remains.insert(i,used_num)，这里的i要插回原来的位置，不能用append。