46. 全排列

题目描述

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

示例 1：

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

示例 2：

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

示例 3：

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

提示：

1 <= nums.length <= 6
-10 <= nums[i] <= 10
nums 中的所有整数 互不相同

解法一：回溯

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24


func permute(nums []int) [][]int {
    n := len(nums)
    used := make([]bool, n)
    var ans [][]int
    var tmp []int
    var backtracking func(cnt int)
    backtracking = func(cnt int) {
        if cnt == n {
            ans = append(ans, append([]int(nil), tmp...))
            return
        }
        for i := 0; i < n; i++ {
            if !used[i] {
                used[i] = true
                tmp = append(tmp, nums[i])
                backtracking(cnt+1)
                tmp = tmp[:len(tmp)-1]
                used[i] = false
            }
        }
    }
    backtracking(0)
    return ans
}