题目链接：https://leetcode.cn/problems/permutations/
思路
这道题要用到回溯法，本质上是在一棵决策树上做DFS，每个节点做选择，递归深入，回退恢复，再做下一个选择。排列组合里，我们要考虑到所有的情况，因此这里的节点就是列表中的元素，比如[1, 2, 3]，那就有三个节点，分别考虑这三个节点在第一位的情况，就能把所有的可能都列举出来：[1,2,3], [1,3,2], [2,1,3], [2,3,1], [3,1,2], [3,2,1]
我们定义一个回溯函数backscattering，传入当前的数组和一个中间变量level，以及最终的结果存储列表result
- 首先判断，如果level到达了len(nums) - 1，那么说明没有元素可以再考虑了，将此时的nums放进result中，然后跳出函数，不继续执行下去
如果level没有达到len(nums) - 1，那就说明还有可能性没有考虑完，需要继续做搜索：
- 从当前的 level 位置开始，依次尝试把每一个候选元素放到 level 这个位置上，因为我每次已经固定了第1个元素（把每一个节点都放到第一个，然后遍历所有的可能性），所以在子循环中，我的i取值范围是[level, len(nums))，尝试后面的每个元素都是否能放到level这个位置
- 为了实现这个操作，代码里用到了 交换：
nums[i], nums[level] = nums[level], nums[i]。这样可以把第 i 个元素放到 level 的位置上，相当于“选择了这个元素” - 做出选择之后，调用递归函数
backscattering(nums, level + 1, result)，进入下一层，去决定下一个位置该放谁 - 当递归返回时，说明这一条选择路径已经搜索结束，为了不影响接下来的其他可能性，需要把之前交换的两个元素 再交换回来，恢复原来的数组状态，这一步就是“回溯”
- 整个 for 循环会把所有能放在 level 位置的元素都尝试一遍，并在递归过程中不断生成新的排列。当所有循环结束时，说明以当前 level 开头的所有情况都考虑完毕，函数返回上层
举例
反思
- 回溯的核心思想就是 枚举 + 恢复，每次在当前位置尝试所有可能的元素，把它放进去，然后继续往下递归搜索；当一条路径走完，就退回来恢复现场，再尝试下一种可能
- 这种“搜索 → 回退 → 再搜索”的过程，就像在一棵“决策树”上做深度优先遍历，最终会遍历出所有排列
- 这个问题中我们递归的是列表的索引值，这点一定要弄清楚，level代表了“侯选位置”的索引
其实回溯的过程可以类比为在一棵 树形结构的决策树 上进行深度优先遍历。它的基本思想是：
- 从根节点出发，沿着某一条路径不断向下递归，直到到达叶子节点（对应于所有位置都被填满，得到一个完整解）；
- 然后回退一步（回溯），撤销上一步的选择，转而尝试下一个可选分支；
- 在当前节点的所有子节点都遍历完成后，再回退到父节点，继续探索父节点的下一个分支；
- 如此反复，直到整棵决策树的所有路径都被遍历。
- 此类题目的套路：在回溯函数中先修改当前节点的状态（如记录，把它append到结果列表中，或者修改为True，表示已经访问），接着递归所有可能的子节点，子节点递归完成后再将当前节点的状态给修改回来，回退，为了实现剪枝降低算法复杂度，在回溯函数的开始可以设置if语句判断条件，在触及边界/特殊情况下及时停止，避免无用功
类推
77 组合，$O(C[N, k])$, $O(k)$，已是最优解，每次循环完了以后要pop一下
79 单词搜索，$O(MN*4)$, $O(MN)$，已是最优解，在遍历的时候会做剪枝，理论上的时间复杂度应该是$O(MN*4^L)$，但因为在回溯函数中设置了条件，“及时止损”，所以复杂度能够降低
结果
时间复杂度：$O(N!)$
空间复杂度：$O(N)$
已是最优解
