解题思路

排列与组合不同的是排列是每个元素顺序不同就算一个新的排列，而组合是不管里面元素的顺序是怎样的。

[1,2,3] 与 [3,2,1]是不同的排列，但是它们是一样的组合

这题我们只需要知道每次遍历剩余哪些元素还没被添加，将其添加就行，唯一的难点就是怎么判断哪些元素没有被添加，我使用的是哈希表，通过记录下标来分辨哪些元素没有被添加。

代码

Python

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
class Solution:
    def permute(self, nums: List[int]) -> List[List[int]]:
        n = len(nums)
        if n == 0:
            return [[]]
        ans = []
        s = set()
        tmp = []
        def dfs():
            # nonlocal ans, s, tmp
            if len(tmp) == n:
                ans.append(tmp.copy())
                return
            for i in range(n):
                if nums[i] in s:
                    continue
                s.add(nums[i])
                tmp.append(nums[i])
                dfs()
                s.remove(tmp.pop())
        dfs()
        return ans

C++

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
class Solution {
public:
    void backtrack(vector<vector<int>>& res, vector<int>& output, int first, int len){
        // 所有数都填完了
        if (first == len) {
            res.emplace_back(output);
            return;
        }
        for (int i = first; i < len; ++i) {
            // 动态维护数组
            swap(output[i], output[first]);
            // 继续递归填下一个数
            backtrack(res, output, first + 1, len);
            // 撤销操作
            swap(output[i], output[first]);
        }
    }
    vector<vector<int>> permute(vector<int>& nums) {
        vector<vector<int> > res;
        backtrack(res, nums, 0, (int)nums.size());
        return res;
    }
};

Go

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
var result [][]int
var path []int
func permute(nums []int) [][]int {
    result = [][]int{}
    path = []int{}
    m := make(map[int]bool)
    backtracking(nums, m)
    return result
}

func backtracking(nums []int, m map[int]bool) {
    if len(path) == len(nums) {
        t := make([]int, len(path))
        copy(t, path)
        result = append(result, t)
    }
    for i := 0; i < len(nums); i++ {
        if m[i] == true {continue}
        m[i] = true
        path = append(path, nums[i])
        backtracking(nums, m)
        path = path[:len(path) - 1]
        m[i] = false
    }
}