回溯算法模板框架

回溯算法框架

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

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

回溯算法demo

window.onload = function () {
    console.log(111111)
    // n = 4; k = 2
    let n = 4, k = 2
    let result = []
    let path = []

    const combine = (n, k) => {
        result =[]
        combineHelper(n, k, 1)
        return result
    }

    const combineHelper = (n, k, startIndex) => {
        if (path.length === k) {
            result.push([...path])
            return
        }
        for (let i = startIndex; i <= n - (k-path.length) + 1; ++i) {
            // 横向遍历
            path.push(i)
            combineHelper(n, k, i+1) //纵向遍历
            path.pop()
        }
    }
    // 1到4之间，所有可能的 2 个数的组合
    combine(4, 2)
    console.log(result,path)
}