LeetCode-46. 全排列 - sheep44044的小站

回溯#

给定一个不含重复数字的数组 nums ，返回其 所有可能的全排列 。你可以 按任意顺序 返回答案。

示例 1：

1
输入：nums = [1,2,3]
2
输出：[[1,2,3],[1,3,2],[2,1,3],[2,3,1],[3,1,2],[3,2,1]]

示例 2：

1
输入：nums = [0,1]
2
输出：[[0,1],[1,0]]

示例 3：

1
输入：nums = [1]
2
输出：[[1]]

1
func permute(nums []int) [][]int {
2
    if len(nums) == 0 {
3
        return nil
4
    }
5

6
    res := [][]int{}
7
    path := []int{}
8
    used := make([]bool, len(nums))
9

10
    var backtrack func()
11
    backtrack = func() {
12
        if len(path) == len(nums) {
13
            res = append(res, append([]int(nil), path...))
14
      return
15
        }
16

17
        for i := 0; i < len(nums); i++ {
18
            if used[i] {
19
                continue
20
            }
21

22
            path = append(path, nums[i])
23
            used[i] = true
24
            backtrack()
25
            path = path[:len(path)-1]
26
            used[i] = false
27
        }
28
    }
29

30
    backtrack()
31
    return res
32
}