Backtracking

[shanejix]

回溯是建立在 DFS 的基础之上的

回溯模板

const res = []

// path 路径
const target = []

const dfs = (source, deep, ...) => { // 状态变量 

    // 递归终止的条件
    if (🤔) {
        // 存储满足条件的结果
        res.push(target.slice())
        // 返回
        return
    }

    // 当前节点 for loop 横向遍历,向下分叉, index 视情况而定
    for (let i = index; i < source.length; i++) {

        // 是否需要剪枝

        // 做出选择
        target.push(source[i]);

        // 深度递归，进入下一层
        dfs(source, 🤔 + 1, ...);

        // 撤销选择
        target.pop();
    }

    return ans;
}