---

[!info] related notes 算法面试题型 MOC DFS / BFS / 回溯

回溯

入门回溯

• 电话号码的字母组合

子集型

子集

每个元素是选还是不选

模板1（输入角度）

• 当前操作？ 枚举第 i 个数选/不选
• 子问题？ 从下标 >= i 的数字中构造子集
• 下一个子问题？ 从下标 >= i+1 的数字中构造子集

var subsets = function(nums) {
    let res = [];
    let path =[];

    function dfs(i) {
        if (i === nums.length) {
            res.push([...path]);
            return;
        }

        dfs(i+1); // 不选，直接跳过当前数，进入下一个数

        path.push(nums[i]);
        dfs(i+1); // 选，添加后进入下一个数
        path.pop();  //恢复现场

    }
    dfs(0);
    return res;
};

模板2（站在答案视角）

• 当前操作？ 枚举 1 个下标 j >= i 的数字加入 path
• 子问题？ 从下标 >= i 的数字中构造子集
• 下一个子问题？ 从下标 >= j+1 的数字中构造子集

每个节点都是答案

var subsets = function (nums) {
    let res = [];
    let path = [];

    function dfs(i) {
        res.push([...path]); // 每个节点都是结果
        if (i === nums.length) {
            return;
        }
        for (let j = i; j < nums.length; j++) {
            path.push(nums[j]);
            dfs(j + 1);
            path.pop();
        }
    }
    dfs(0);
    return res;
};

划分型回溯

把分割线（逗号）看成是可以「选或不选」的东西，本质是子集型回溯。

组合型

排列型