回溯算法（思想）

回溯算法

可以理解为不撞南墙不回头的暴力穷举

适用的问题类型：

• 组合（没有顺序，[1, 2] 和 [2, 1]是相同的，不能走回头路，关键index）
• 切割
• 子集（收集所有节点，和组合一样不能回头，关键index，进递归就收集）
• 排列（有顺序，[1, 2] 和 [2, 1]是不同的，可以回头，但不能选自己，用used数组标记是否已在）
• 棋盘

组合问题

关键词：startIndex(起始索引)：一路向后，不回头

const result = [] //存放最终结果
const path = []; //存放当前路径（比如已经选了哪些数）
// 组合：需要 startIndex
function backtrack(nums, startIndex) {
    // ... 收集结果 ...
    if (满足结束条件) {
        //不能直接push进去path，相当于是对数组的引用，push改变内容也会变
        result.push([...path])
        return;
    }
    // 核心区别 A：循环从 startIndex 开始
    // 意味着：前面的数字我已经处理过了，以后再也不看它们了
    for (let i = startIndex; i < nums.length; i++) {
        
        path.push(nums[i]);
        
        // 核心区别 B：递归时传 i + 1
        // 意味着：下一层只能从当前数字的屁股后面开始选
        backtrack(nums, i + 1); 
        
        path.pop();
    }
}

排列问题

关键词：used数组（记录谁被用了）

// 排列：不需要 startIndex，但需要 used 数组
function backtrack(nums, used) {
    // ... 收集结果 ...

    // 核心区别 A：循环永远从 0 开始
    // 意味着：每次都要看全班同学，谁没排队我就选谁
    for (let i = 0; i < nums.length; i++) {
        
        // 核心区别 B：用 used 数组跳过已经选在这个排列里的数字
        if (used[i]) continue; 

        used[i] = true; // 标记：这个数字我占了
        path.push(nums[i]);
        
        // 递归：不需要传索引，只需要传状态
        backtrack(nums, used); 
        
        path.pop();
        used[i] = false; // 回溯：释放这个数字
    }
}

子集问题

function subsets(nums) {
    const res = [], path = [];
    
    function backtrack(startIndex) {
        // 只要进来了，就是一个子集，直接收集
        res.push([...path]);
        
        for (let i = startIndex; i < nums.length; i++) {
            path.push(nums[i]);
            backtrack(i + 1);
            path.pop();
        }
    }
    backtrack(0);
    return res;
}

灵魂拷问：为什么组合要用 startIndex？

假设数组是 [1, 2, 3]，我们要找大小为 2 的组合。

1. 第一轮选 1：

  剩下的能选 [2, 3]。

1. 第一轮选 2：

1. 第一轮选 3：
     后面没数了，结束。

结论：startIndex 的作用就是**“去重”**，它强行规定了元素的相对顺序（必须是索引小的在前，大的在后），从而避免了 [2, 1] 这种逆序的重复组合出现。

优化

回溯算法因为是暴力穷举，所以剪枝很重要（提前结束不必要的循环）

例子：比如你想在 [1...10] 里选 5 个数。如果 startIndex 已经到了 8（只剩 8, 9, 10），那你根本凑不齐 5 个数了。

• 未剪枝：i < nums.length
• 剪枝后：i <= nums.length - (k - path.length) (意思是：剩下的元素必须够填满空位，否则别循环了)

问题变形

不管题目如何，只要是回溯，核心就是一棵树