回溯

介绍

回溯定义是：

简单来说，回溯是一种逐步尝试寻找解的过程，如果当前尝试失败，就返回上一步（即“回溯”），尝试其他可能的路径。

可以理解为一个进阶版的递归与树 DFS 的结合。

核心观点

1. 选择 DFS 遍历对象
2. 确定约束条件：DFS 变量结果不可能全部有效，我们需要找到有效的部分，也就是说需要进行“充分剪枝”。
3. 确定 DFS 遍历结束的边界：设定目标，确保回溯能够正确终止。

---

题目

括号生成

题目描述

数字 n 代表生成括号的对数，请你设计一个函数，能够生成所有可能的并且 有效的 括号组合。

解题思路

• 选择

  • 在这里，每次最多有两个选择：选左括号或右括号。
  • “选择”会展开出一棵解的空间树，使用 DFS 遍历这棵树，找出所有的解，这个过程就是回溯。

• 约束条件

  • 什么时候可以选左括号？什么时候可以选右括号？
  • 利用约束做“剪枝”，去掉不会产生解的选项。
  • 例如 ()，如果左右括号各剩一个，再选 ) 就会变成 ())，这种情况不合法，因此剪枝：

  if (right > left) { // 右括号剩的比较多，才能选右括号
      dfs(str + ')', left, right - 1);
  }

• 目标

  • 当构建的字符串长度达到 2 * n 时，就可以结束递归。

代码实现

/**
 * @param {number} n
 * @return {string[]}
 */
var generateParenthesis = function(n) {
    const res = [];
    
    const dfs = (lRemain, rRemain, str) => {
        if (str.length === 2 * n) {
            res.push(str);
            return;
        }
        
        if (lRemain > 0) {
            dfs(lRemain - 1, rRemain, str + "(");
        }
        
        if (lRemain < rRemain) {
            dfs(lRemain, rRemain - 1, str + ")");
        }
    };
    
    dfs(n, n, "");
    return res;
};

---

组合总和

题目描述

给你一个 无重复元素 的整数数组 candidates 和一个目标整数 target，找出 candidates 中所有 不同组合，使得数字和为 target，并以列表形式返回。

• 你可以按 任意顺序 返回这些组合。
• candidates 中的 同一个数字 可以 无限制重复被选取。
• 如果至少一个数字的被选数量不同，则两种组合被视为不同。

解题思路

本题的关键是如何避免重复，确保不同的组合：

• 只要限制 下一次选择的起点，即基于本次的选择，下一次就不会选到本次选择同层左边的数。
• 通过 控制 for 遍历的起点，去掉会产生重复组合的选项。

示例代码中的 for 循环体现了这一点：

for (let i = start; i < candidates.length; i++) { // 枚举当前可选的数，从 start 开始 
    temp.push(candidates[i]); // 选这个数 
    dfs(i, temp, sum + candidates[i]); // 基于此，继续选择，传 i，下次就不会选到 i 左边的数 
    temp.pop(); // 撤销选择，回到选择 candidates[i] 之前的状态，继续尝试选同层右边的数 
}

代码实现

/**
 * @param {number[]} candidates
 * @param {number} target
 * @return {number[][]}
 */
var combinationSum = function(candidates, target) {
    const res = [];
    
    const dfs = (start, temp, sum) => {
        if (sum >= target) {
            if (sum === target) {
                res.push(temp.slice());
            }
            return;
        }
        
        for (let i = start; i < candidates.length; i++) {
            temp.push(candidates[i]);
            dfs(i, temp, sum + candidates[i]);
            temp.pop();
        }
    };
    
    dfs(0, [], 0);
    return res;
};

---