回溯算法解题套路模板：从排列与组合为案例开讲

回溯算法网上教程很多，这里是一个毕竟合集

【代码随想录】带你学透回溯算法（理论篇）| 回溯法精讲！ https://www.bilibili.com/video/BV1cy4y167mM/

【labuladong】回溯算法核心套路详解 https://www.bilibili.com/video/BV1P5411N7Xc/

【labuladong】回溯算法秒杀所有排列/组合/子集问题 https://www.bilibili.com/video/BV1Yt4y1t7dK/

什么是回溯法（Backtracking）

回溯法也可以叫做回溯搜索法，它是一种搜索的方式：采用试错的思想，在搜索尝试过程中寻找问题的解，当探索到某一步时，发现原先的选择并不满足求解条件，或者还需要满足更多求解条件时，就退回一步（回溯）重新选择，这种走不通就退回再走的技术称为「回溯法」，而满足回溯条件的某个状态的点称为「回溯点」。

简单来说，回溯算法采用了一种 「走不通就回退」 的算法思想。

回溯是递归的副产品，只要有递归就会有回溯——回溯函数也就是递归函数，指的都是一个函数。

• 循环：不断重复进行某一运算、操作。
  

• 迭代：不断对前一旧值运算得到新值直到达到精度。一般用于得到近似目标值，反复循环同一运算式（函数），并且总是把前一 次运算结果反代会运算式进行下一次运算

• 递推：从初值出发反复进行某一运算得到所需结果。-----从已知到未知，从小到达（比如每年长高9cm，20年180，30后270）

• 回溯：递归时经历的一个过程。

• 递归：从所需结果出发不断回溯前一运算直到回到初值再递推得到所需结果----从未知到已知，从大到小，再从小到大(你想进bat，那么编程就的牛逼，就得卸载玩者农药，努力学习）。递归(Recursion)是从归纳法(Induction)衍生出来的。

具体查看：《再谈循环&迭代&回溯&递归&递推这些基本概念》

回溯法模板

回溯法一般是在集合中递归搜索，集合的大小构成了树的宽度，递归的深度构成的树的深度。

回溯算法是在遍历「树枝」，DFS 算法是在遍历「节点」

抽象地说，解决一个回溯问题，实际上就是遍历一棵决策树的过程，树的每个叶子节点存放着一个合法答案。你把整棵树遍历一遍，把叶子节点上的答案都收集起来，就能得到所有的合法答案。

站在回溯树的一个节点上，你只需要思考 3 个问题：

1. 路径：也就是已经做出的选择。

2. 选择列表：也就是你当前可以做的选择。

3. 结束条件：也就是到达决策树底层，无法再做选择的条件。

回溯算法的框架：

回溯函数遍历过程伪代码如下：

for (选择：本层集合中元素（树中节点孩子的数量就是集合的大小）) {
    处理节点;
    backtracking(路径，选择列表); // 递归
    回溯，撤销处理结果
}

从图中看出for循环可以理解是横向遍历，backtracking（递归）就是纵向遍历，这样就把这棵树全遍历完了，一般来说，搜索叶子节点就是找的其中一个结果了。

回溯算法模板框架

void backtracking(参数) {
    if (终止条件) {
        存放结果;
        return;
    }

    for (选择：本层集合中元素（树中节点孩子的数量就是集合的大小）) {
        处理节点;
        backtracking(路径，选择列表); // 递归
        回溯，撤销处理结果
    }
}

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

回溯算法三步走

回溯算法的基本思想是：以深度优先搜索的方式，根据产生子节点的条件约束，搜索问题的解。当发现当前节点已不满足求解条件时，就「回溯」返回，尝试其他的路径。

那么，在写回溯算法时，我们可以按照这个思想来书写回溯算法，具体步骤如下：

1. 明确所有选择：画出搜索过程的决策树，根据决策树来确定搜索路径。

2. 明确终止条件：推敲出递归的终止条件，以及递归终止时的要执行的处理方法。

3. 将决策树和终止条件翻译成代码：

1. 定义回溯函数（明确函数意义、传入参数、返回结果等）。

2. 书写回溯函数主体（给出约束条件、选择元素、递归搜索、撤销选择部分）。

3. 明确递归终止条件（给出递归终止条件，以及递归终止时的处理方法）。

回溯法的效率

因为回溯的本质是穷举，穷举所有可能，然后选出我们想要的答案，如果想让回溯法高效一些，可以加一些剪枝的操作，但也改不了回溯法就是穷举的本质。

那么既然回溯法并不高效为什么还要用它呢？

因为没得选，一些问题能暴力搜出来就不错了，撑死了再剪枝一下，还没有更高效的解法。

此时大家应该好奇了，都什么问题，这么牛逼，只能暴力搜索。

回溯法解决的问题

排列组合子集大纲

无论是排列、组合还是子集问题，简单说无非就是让你从序列 nums 中以给定规则取若干元素，主要有以下几种变体：

形式一：元素无重不可复选，即 nums 中的元素都是唯一的，每个元素最多只能被使用一次，这也是最基本的形式。

以组合为例，如果输入 nums = [2,3,6,7]，和为 7 的组合应该只有 [7]。

形式二：元素可重不可复选，即 nums 中的元素可以存在重复，每个元素最多只能被使用一次。

以组合为例，如果输入 nums = [2,5,2,1,2]，和为 7 的组合应该有两种 [2,2,2,1] 和 [5,2]。

形式三：元素无重可复选，即 nums 中的元素都是唯一的，每个元素可以被使用若干次。

以组合为例，如果输入 nums = [2,3,6,7]，和为 7 的组合应该有两种 [2,2,3] 和 [7]。

形式四：元素可重可复选。但既然元素可复选，那又何必存在重复元素呢？元素去重之后就等同于形式三，所以这种情况不用考虑。

上面用组合问题举的例子，但排列、组合、子集问题都可以有这三种基本形式，所以共有 9 种变化。

除此之外，题目也可以再添加各种限制条件，比如让你求和为 target 且元素个数为 k 的组合，那这么一来又可以衍生出一堆变体，怪不得面试笔试中经常考到排列组合这种基本题型。

但无论形式怎么变化，其本质就是穷举所有解，而这些解呈现树形结构，所以合理使用回溯算法框架，稍改代码框架即可把这些问题一网打尽。

组合

给定两个整数 n 和 k，返回范围 [1, n] 中所有可能的 k 个数的组合。

你可以按 任何顺序 返回答案。

示例: 输入: n = 4, k = 2 输出: [ [2,4], [3,4], [2,3], [1,2], [1,3], [1,4], ]

本题是回溯法的经典题目。

思路

直接的解法当然是使用for循环

例如示例中k为2，很容易想到 用两个for循环，这样就可以输出 和示例中一样的结果。

int n = 4;
for (int i = 1; i <= n; i++) {
    for (int j = i + 1; j <= n; j++) {
        cout << i << " " << j << endl;
    }
}

n = 100, k = 3 那么就三层for循环，代码如下：

int n = 100;
for (int i = 1; i <= n; i++) {
    for (int j = i + 1; j <= n; j++) {
        for (int u = j + 1; u <= n; n++) {
            cout << i << " " << j << " " << u << endl;
        }
    }
}

如果n为100，k为50呢，那就50层for循环，是不是开始窒息。

此时就会发现虽然想暴力搜索，但是用for循环嵌套连暴力都写不出来！

回溯搜索法来了，虽然回溯法也是暴力，但至少能写出来，不像for循环嵌套k层让人绝望。

回溯法怎么暴力搜呢？

上面我们说了要解决 n为100，k为50的情况，暴力写法需要嵌套50层for循环，那么回溯法就用递归来解决嵌套层数的问题。

递归来做层叠嵌套（可以理解是开k层for循环），每一次的递归中嵌套一个for循环，那么递归就可以用于解决多层嵌套循环的问题了。

把组合问题抽象为如下树形结构：

最终代码

var combine = function(n, k) {
  const result = []; // 用于存储所有可能的组合结果
  const backtrack = (start, path) => {
    if (path.length === k) {// 如果路径长度等于 k，说明找到了一个有效的组合
      result.push([...path]);
      return;
    }
    for (let i = start; i <= n; i++) {// 从 start 开始，尝试添加下一个数字到路径中
      path.push(i); // 尝试添加当前数字到路径中
      backtrack(i + 1, path); // 递归地寻找下一个数字
      path.pop(); // 回溯，移除最后一个添加的数字
    }
  };

  backtrack(1, []); // 从数字 1 开始，初始路径为空
  return result;
};

结合减枝优化

使用减枝（剪枝）技术可以显著提高效率，特别是在组合数目很大时。

图中每一个节点（图中为矩形），就代表本层的一个for循环，那么每一层的for循环从第二个数开始遍历的话，都没有意义，都是无效遍历。

所以，可以剪枝的地方就在递归中每一层的for循环所选择的起始位置。

如果for循环选择的起始位置之后的元素个数 已经不足 我们需要的元素个数了，那么就没有必要搜索了。

所以优化之后的for循环是：

for (let i = startIndex; i <= n - (k - path.size()) + 1; i++) // i为本次搜索的起始位置

优化后整体代码如下：

function combine(n, k) {
  const results = [];
  function backtrack(start, path) {
    if (path.length === k) {
      results.push([...path]);
      return;
    }
    // 优化：剩余的数字不足以凑齐 k 个组合，则无需继续向下搜索
    for (let i = start; i <= n && n - i + 1 >= k - path.length; i++) {
      path.push(i);
      backtrack(i + 1, path);
      path.pop();
    }
  }
  backtrack(1, []);
  return results;
}

组合总和集合

• 39.组合总和

• 40.组合总和II

• 216.组合总和III

组合总和III

找出所有相加之和为 n 的 k 个数的组合。组合中只允许含有 1 - 9 的正整数，并且每种组合中不存在重复的数字。

说明：1、所有数字都是正整数，2、解集不能包含重复的组合。

示例 1: 输入: k = 3, n = 7 输出: [[1,2,4]]

示例 2: 输入: k = 3, n = 9 输出: [[1,2,6], [1,3,5], [2,3,4]]

相对上一题（77.组合），本题是简单一些了： 本题就是在[1,2,3,4,5,6,7,8,9]这个集合中找到和为n的k个数的组合。

本题k相当于树的深度，9（因为整个集合就是9个数）就是树的宽度。

最终代码：

其实只需加个条件即可：if (sum === n)  results.push([...path]);

function combinationSum3(k, n) {
  const results = [];
  function backtrack(start, path) {
    if (path.length === k) {
      const sum = path.reduce((acc, val) => acc + val, 0);
      if (sum === n) {
        results.push([...path]);
      }
      return;
    }
    for (let i = start; i <= 9; i++) {
      path.push(i);
      backtrack(i + 1, path);
      path.pop();
    }
  }
  backtrack(1, []);
  return results;
}

剪枝优化

剩余的数字不足以凑齐 k 个组合，或者已经超过目标和 n，则无需继续搜索

for (let i = start; i <= 9 && current.length + (9 - i + 1) >= k; i++) {
}

组合总和

给定一个无重复元素的数组 candidates 和一个目标数 target ，找出 candidates 中所有可以使数字和为 target 的组合。

candidates 中的数字可以无限制重复被选取。

示例 1：输入：candidates = [2,3,6,7], target = 7,   所求解集为： [ [7], [2,2,3] ]

示例 2：输入：candidates = [2,3,5], target = 8,      所求解集为： [ [2,2,2,2], [2,3,3], [3,5] ]

本题和77.组合 (opens new window)，216.组合总和III (opens new window)的区别是：本题没有数量要求，可以无限重复，但是有总和的限制，所以间接的也是有个数的限制。

本题搜索的过程抽象成树形结构如下：

注意图中叶子节点的返回条件，因为本题没有组合数量要求，仅仅是总和的限制，所以递归没有层数的限制，只要选取的元素总和超过target，就返回！

而在77.组合 (opens new window)和216.组合总和III (opens new window)中都可以知道要递归K层，因为要取k个元素的组合。

function combinationSum(candidates, target) {
  const results = [];
  function backtrack(start, current, currentSum) {
    if (currentSum === target) {
      results.push([...current]);
      return;
    }
    for (let i = start; i < candidates.length; i++) {//遍历从 start 到 candidates.length - 1 的所有候选数字。
      if (currentSum + candidates[i] <= target) {//如果符合条件 current 中，并递归调用 backtrack 函数。
        current.push(candidates[i]);
        backtrack(i, current, currentSum + candidates[i]);
        current.pop();//当递归返回时，弹出最后添加的数字，回溯到上一层状态，继续选择下一个候选数字。
      }
    }
  }
  //  candidates.sort((a, b) => a - b); // 首先对候选数组进行排序,进行剪枝优化
  backtrack(0, [], 0);
  return results;
}

使用剪枝优化

对于sum已经大于target的情况，其实是依然进入了下一层递归，只是下一层递归结束判断的时候，会判断sum > target的话就返回。

其实如果已经知道下一层的sum会大于target，就没有必要进入下一层递归了。

那么可以在for循环的搜索范围上做做文章了。

对总集合排序之后，如果下一层的sum（就是本层的 sum + candidates[i]）已经大于target，就可以结束本轮for循环的遍历。

剪枝优化

• 剪枝条件： 在循环选择候选数字时，没有显式添加额外的剪枝条件，但是在这里排序 candidates 数组可以使得我们在尽早排除不可能的组合情况，从而优化搜索过程。

• 排序 candidates 数组： 在开始搜索之前，我们首先对 candidates 数组进行排序。这样做的好处是，当我们选择了某个元素时，可以尽快排除不符合条件的后续元素，从而减少不必要的搜索。

• 效果： 这种优化可以有效地减少搜索空间，特别是当 candidates 数组较大或者目标和 target 较小的情况下，效果更为明显。

组合总和II

给定一个数组 candidates 和一个目标数 target ，找出 candidates 中所有可以使数字和为 target 的组合。

candidates 中的每个数字在每个组合中只能使用一次。

说明： 所有数字（包括目标数）都是正整数。解集不能包含重复的组合。

示例 1:   输入: candidates = [10,1,2,7,6,1,5], target = 8,  所求解集为:  [[1, 7], [1, 2, 5], [2, 6], [1, 1, 6] ]

示例 2:   输入: candidates = [2,5,2,1,2], target = 5,          所求解集为:  [[1,2,2],  [5]]

这道题目和39.组合总和(opens new window)如下区别：

• 本题candidates 中的每个数字在每个组合中只能使用一次。

• 本题数组candidates的元素是有重复的，而39.组合总和 (opens new window)是无重复元素的数组candidates

最后本题和39.组合总和 (opens new window)要求一样，解集不能包含重复的组合。

本题的难点在于区别2中：集合（数组candidates）有重复元素，但还不能有重复的组合。

怎么去重？

这个去重为什么很难理解呢，所谓去重，其实就是使用过的元素不能重复选取。

都知道组合问题可以抽象为树形结构，那么“使用过”在这个树形结构上是有两个维度的，一个维度是同一树枝上使用过，一个维度是同一树层上使用过。没有理解这两个层面上的“使用过” 是造成大家没有彻底理解去重的根本原因。

那么问题来了，我们是要同一树层上使用过，还是同一树枝上使用过呢？

回看一下题目，元素在同一个组合内是可以重复的，怎么重复都没事，但两个组合不能相同。

所以我们要去重的是同一树层上的“使用过”，同一树枝上的都是一个组合里的元素，不用去重。

为了理解去重我们来举一个例子，candidates = [1, 1, 2], target = 3，（方便起见candidates已经排序了）

强调一下，树层去重的话，需要对数组排序！

选择过程树形结构如图所示：

可以看到图中，每个节点相对于 39.组合总和 (opens new window)我多加了used数组，这个used数组下面会重点介绍。

function combinationSum2(candidates, target) {
  const results = [];
  candidates.sort((a, b) => a - b);//方便处理重复的数字
  function backtrack(start, current, currentSum) {
    if (currentSum === target) {
      results.push([...current]);
      return;
    }

    for (let i = start; i < candidates.length; i++) {//从 start 到 candidates.length - 1 的所有候选数字。
      if (i > start && candidates[i] === candidates[i - 1]) continue; // 跳过重复的数字
      if (currentSum + candidates[i] <= target) {
        current.push(candidates[i]);
        // 和39.组合总和的区别1：这里是i+1，每个数字在每个组合中只能使用一次
        backtrack(i + 1, current, currentSum + candidates[i]);
        current.pop();
      } else {// 剪枝：当前数字已经大于目标和，后续数字也必然大于目标和，不需要继续搜索
        break; 
      }
    }
  }
  backtrack(0, [], 0);
  return results;
}

因为本题已经对数组进行排序，所以不必要使用used 进一步去去重、

排列

46.全排列

47.全排列 II

全排列

给定一个 没有重复 数字的序列，返回其所有可能的全排列。

示例:   输入: [1,2,3]   输出: [ [1,2,3], [1,3,2], [2,1,3], [2,3,1], [3,1,2], [3,2,1] ]

以[1,2,3]为例，抽象成树形结构如下：

最终代码

function permute(nums) {
  const results = [];
  function backtrack(current) {
    if (current.length === nums.length) {//当 current 的长度等于 nums 的长度时，说明已经形成了一个完整的排列
      results.push([...current]);
      return;
    }
    for (let i = 0; i < nums.length; i++) {
      if (!current.includes(nums[i])) { // 确保当前数字不在当前排列中
        current.push(nums[i]);
        backtrack(current);
        current.pop();
      }
    }
  }
  backtrack([]);
  return results;
}

全排列 II

给定一个可包含重复数字的序列 nums ，按任意顺序 返回所有不重复的全排列。

示例 1：  输入：nums = [1,1,2]   输出： [[1,1,2], [1,2,1], [2,1,1]]

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

这道题目和46.全排列 (opens new window)的区别在与给定一个可包含重复数字的序列，要返回所有不重复的全排列。

在40.组合总和II (opens new window)、90.子集II (opens new window)我们分别详细讲解了组合问题和子集问题如何去重。

那么排列问题其实也是一样的套路：去重一定要对元素进行排序。

以示例中的 [1,1,2]为例 （为了方便举例，已经排序）抽象为一棵树，去重过程如图：

图中我们对同一树层，前一位（也就是nums[i-1]）如果使用过，那么就进行去重。

一般来说：组合问题和排列问题是在树形结构的叶子节点上收集结果，而子集问题就是取树上所有节点的结果。

function permuteUnique(nums) {
  const results = [];
  nums.sort((a, b) => a - b); // 排序后，相同的数字会相邻，方便进行去重操作
  function backtrack(current, used) {
    if (current.length === nums.length) {//已经形成了一个完整的排列
      results.push([...current]);
      return;
    }
    for (let i = 0; i < nums.length; i++) {
      if (used[i] || (i > 0 && nums[i] === nums[i - 1] && !used[i - 1])) {
        continue; // 跳过重复选择的数字
      }
      current.push(nums[i]);
      used[i] = true;
      backtrack(current, used);
      used[i] = false;
      current.pop();
    }
  }
  backtrack([], new Array(nums.length).fill(false));
  return results;
}

为什么还需要 used 数组去重？

• 处理排序后的连续重复情况：虽然排序后相同的数字在一起（仅保证了相同数字的连续性，而并未标记其使用状态），但是在回溯的过程中，我们依然需要判断某个数字是否已经被选择过，以避免生成重复的排列。

• 确保每个数字只被使用一次：使用 used 数组的目的是在递归过程中标记哪些数字已经被使用过，从而确保每个数字只能被使用一次，从而保证了生成的每个排列的唯一性。

在回溯的过程中，我们需要跳过已经使用过的数字，同时对于相同的数字，只允许其第一个未被使用的出现来避免重复生成相同的排列。

参考文章：

https://programmercarl.com/回溯算法理论基础.html

https://algo.itcharge.cn/09.Algorithm-Base/04.Backtracking-Algorithm/

https://labuladong.online/algo/essential-technique/backtrack-framework/

转载本站文章《回溯算法解题套路模板：从排列与组合为案例开讲》,
请注明出处：https://www.zhoulujun.cn/html/theory/algorithm/leetcode/9163.html