题目描述

给定一个不含重复数字的数组 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]]

题解

回溯本质还是一种DFS的一种，回溯法=DFS+剪枝。
根节点出发搜索空间树，搜索任意节点是否包含问题的解，不包含就回溯，否则，继续进行深度优先搜索。通过一些剪支算法，可以进一步优化搜索空间。
回溯会生成一个状态数，和机器学习中的决策树类似，只不过决策树的树枝和节点的生成要依赖于熵和信息增益。剪枝算法更类似于决策树的预剪支算法，在已知生成这个分支对模型的泛化能力不会那就不生成这个节点，对应到回溯算法中，即不在往这条分支往下走。具体回溯和剪支怎么使用还需看具体条件。

回溯模板伪代码

//backtrack pseudocode
void backtrack() {
    if (stop condition) {
        do something
        return
    }
    for (all conditions) {
        if (not match the requirement) return
        some operation
        backtrack()
        recall operation
    }
}

代码

class Solution {
    private lateinit var used:BooleanArray
    fun permute(nums: IntArray): List<List<Int>> {
        val n = nums.size
        used = BooleanArray(n)
        val res = ArrayList<LinkedList<Int>>()  // 所有排列结果
        val temp = LinkedList<Int>()  // 当前排列
        backtrack(nums,res,temp)
        return res
    }
    private fun backtrack(nums: IntArray,res: ArrayList<LinkedList<Int>>, temp:LinkedList<Int>) {
        // 当前排列的长度等于原数组的长度，已经生成一个完整排列
        if (temp.size == nums.size) {
            res.add(LinkedList<Int>(temp))
            return
        }
        for (i in 0 until nums.size) {
            if (used[i])continue
            used[i] = true
            temp.add(nums[i])
            backtrack(nums, res, temp)
            used[i] = false
            temp.removeLast()
        }
    }
}

图解

假设输入数组为 [1, 2, 3]

初始调用
1
2
3
nums = [1, 2, 3]
res = []
temp = []

第一层递归

   temp = [1]           temp = [2]          temp = [3]
   used = [true, false, false]   used = [false, true, false]   used = [false, false, true]
   ```   

3. 第二层递归
   
    ```bash
    temp = [1, 2]        temp = [1, 3]        temp = [2, 1]
    used = [true, true, false]  used = [true, false, true]  used = [true, true, false]

第三层递归

1 2	temp = [1, 2, 3] temp = [1, 3, 2] temp = [2, 1, 3] used = [true, true, true] used = [true, true, true] used = [true, true, true]

完成一个排列，回溯

1 2	res = [[1, 2, 3]] res = [[1, 2, 3], [1, 3, 2]] res = [[1, 2, 3], [1, 3, 2], [2, 1, 3]] temp = [1, 2] temp = [1, 3] temp = [2, 1]