全排列

解题思路

解决一个回溯问题，实际上就是一个解决策树的遍历过程。你只需要思考3个问题：

1、 路径：也就是已经做出的选择。
2、 选择列表：也就是你当前可以做的选择。
3、 结束条件：也就是到达决策树底层，无法再做选择的条件。

回溯算法的框架

result = []
def backtrack(路径, 选择列表):
  if 满足结束条件：
    result.add(路径);
    return
 for 选择 in 选择列表： 做选择 backtrack(路径, 选择列表); 撤销选择 

其实核心就是 for 循环里面的递归，在递归调用之前「做选择」，在递归调用之后「撤销选择」，特别简单。

什么叫做选择和撤销选择？这个框架的底层原理是什么？

全排列问题 “全排列”就是一个非常经典的“回溯”算法俄应用。我们直到 N 个数字的全排列一共有 N!这么多个。

大家可以尝试一下在纸上写3个数字、4个数字、5个数字的全排列，相信不难找到这样的方法。

以数组[1, 2, 3]的全排列为例：

• 以 1 开头的全排列，它们是： [1, 2, 3],[1,3,2];
• 以 2 开头的全排列，它们是： [2, 1, 3],[2, 3, 1];
• 最后3开头的全排列，它们是： [3, 1, 2],[3, 2, 1];

你也可以直接画出如下这颗回溯树：只要从根遍历这棵树，记录路径上的数字，其实就是所有的全排列。我们不妨把这颗树称为回溯算法的「决策树」

为啥说这是决策树呢？因为你在每个节点上其实都在做决策。比如说你站在下图的红色节点上：

你选择就在做决策，可以选择 1 那条树枝，也可以选择3那条树枝。为啥只能在1 和 3 之中选择呢？因为 2 这个树枝在你身后，这个选择你之前做过了，而全排列是不允重复使用数字的。

现在可以解答开头的几个名词：[2] 就是 「路径」，记录你已经做过的选； [1,3] 就是「选择列表」，表示你当前可以做出的选择；「结束条件」就是遍历到树的底层，在这里就是选择列表为空的时候。

如果明白了这几个词，可以把 「路径」 和 「选择列表」作为决策树上每个节点的属性，比如下图列出了几个节点的属性：

我们定义的 backtrack 函数其实就像一个指针，在这颗树上游走，同时要正确维护每个节点的属性，每当走到树的底层，其「路径」就是一个全排列。

再进一步，如何遍历一颗树？这个不应该不难吧。各种搜索问题其实都是树的遍历问题，而多叉树的遍历框架就是这样：

void traverse(TreeNode root) {
    for (TreeNode child : root.childern)
        // 前序遍历需要的操作
        traverse(child);
        // 后序遍历需要的操作
} 

而所谓的前序遍历和后序比那里，它们只是两个很有用的时间点，我给你画张图你就明白了：

前序遍历的代码在进入某一个节点之前的那个时间点执行，后序遍历代码在离开某个节点之后的那个时间点执行。

回想我们刚才说的，「路径」和 「选择」是每个节点的属性，函数在树上游走要正确维护节点的属性，那么就要在这两个特殊时间点搞点动作：

现在，你是否理解了回溯算法的这段核心框架？

for 选择 in 选择列表：
    # 做选择
    将该选择从选择列表移除
    路径.add(选择)
    backtrack(路径, 选择列表)
 # 撤销选择 路径.remove(选择); 将该选择再加入选择列表 

我们只要在递归之前做出选择，在递归之后撤销刚才的选择，就能正确得到每个节点的选择列表和路径。

下面，直接看全排列代码：

class Solution {
    // 返回值
    List<List<Integer>> res = new LinkedList<>();
    public List<List<Integer>> permute(int[] nums) {
        if(nums == null || nums.length <= 0) return res;
 // 记录「路径」 LinkedList<Integer> track = new LinkedList<>(); backtrack(nums, track); return res; } // 路径：记录在 track 中 // 选择列表：nums 中不存在于 track 的那些元素 // 结束条件：nums 中元素全部在track中 private void backtrack(int[] nums, LinkedList<Integer> track) { // 触发结束条件 if (track.size() == nums.length) { res.add(new LinkedList(track)); return; } for (int i = 0; i < nums.length; i++) { // 排除不合法的选择 if (track.contains(nums[i])) { continue; } // 做选择 track.add(nums[i]); // 进入下一层决策树 backtrack(nums, track); // 取消选择 track.removeLast(); } } } 

我们这里稍微做了些变通，没有显示记录「选择列表」，而是通过 nums 和 track 推导除当前的选择列表：

至此，我们就通过全排列问题详解了回溯算法的底层原理。当然，这个算法解决全排列不是很高效，因为对链表使用 contains 方法需要 O(N) 的时间复杂度。有更好的方法通过交换元素达到目的，但是难理解一些。

class Solution {
    // 定义全局返回值
    List<List<Integer>> res = new LinkedList<>();
    public List<List<Integer>> permute(int[] nums) {
        if (nums == null || nums.length <= 0) return res;
 ArrayList<Integer> track = new ArrayList<Integer>(); for (int num : nums) track.add(num); int n = nums.length; backtrack(n, track, 0); return res; } private void backtrack(int n, List<Integer> track,int first) { // 所有的都填完了 if (first == n) { res.add(new LinkedList<>(track)); return; } for (int i = first; i < n; i++) { // 动态维护数组 Collections.swap(track, first, i); // 进入决策树下一层 backtrack(n, track, first + 1); // 撤销操作 Collections.swap(track, first, i); } } } 

但是必须说明的是，不管这么优化，都符合回溯框架，而且时间复杂度都不可能低于O(N!),因为穷举整颗决策树是无法避免的。这也是回溯算法的一个特点，不像动态规划存在重叠子问题可以优化，回溯算法就是纯暴力穷举，复杂度一般都很高