# 46. 全排列

[https://leetcode-cn.com/problems/permutations/](https://leetcode-cn.com/problems/permutations/)

## 解法一：回溯

每层递归都遍历nums，遇到重复就跳过，否则加入tmplist，直到tmp和nums等长，就得到一个结果

```python
class Solution:
    def permute(self, nums: List[int]) -> List[List[int]]:
        self.res = []    #全局结果
        tmpList = []    #工作数组
        self.backtrack(nums, tmpList)
        return self.res
    
    def backtrack(self, nums, tmpList):
        if len(tmpList) == len(nums):    #递归出口
            self.res.append(list(tmpList))
        for i in nums:
            if i in tmpList:    #去重
                continue
            self.backtrack(nums, tmpList + [i])
```

2020.3.26

```python
class Solution:
    def permute(self, nums: List[int]) -> List[List[int]]:
        def dfs(tmp):
            if len(tmp) == n:
                res.append(list(tmp))
            else:
                for num in nums:
                    if num in tmp:
                        continue
                    dfs(tmp + [num])
                    
        n = len(nums)
        res = []
        dfs([])
        return res
```
