组合

Question

给定两个整数 n 和 k，返回范围 [1, n] 中所有可能的 k 个数的组合。

你可以按 任何顺序 返回答案。

思路

每次从集合中选取元素，可选择的范围随着选择的进行而收缩，调整可选择的范围。

图中可以发现n相当于树的宽度，k相当于树的深度。

那么如何在这个树上遍历，然后收集到我们要的结果集呢？

图中每次搜索到了叶子节点，我们就找到了一个结果。

相当于只需要把达到叶子节点的结果收集起来，就可以求得 n个数中k个数的组合集合。

// if (终止条件) {
//     存放结果;
//     return;
// }

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

var combine = function(n, k) {
    const res = []  // 结果[][]
    const path = [] // 每次递归的结果[]
    // startIndex ：每次递归的起使位置
    const backtracking = (n, k, startIndex)=>{
        if(path.length===k){		// 终止条件
            res.push([...path])		// 存放结果
            return
        }
        for(let i=startIndex;i<=n;i++){	// 本层集合中元素
            path.push(i)				// 处理节点
            backtracking(n,k,i+1)		// 递归
            path.pop()					//回溯
        }
        console.log(res,path)
    }
    backtracking(n,k,1)
    return res
};

这样做是没错的，但是时间上超限了

剪枝优化

图中每一个节点（图中为矩形），就代表本层的一个for循环，那么每一层的for循环从第二个数开始遍历的话，都没有意义，都是无效遍历。

所以，可以剪枝的地方就在递归中每一层的for循环所选择的起始位置。

如果for循环选择的起始位置之后的元素个数已经不足我们需要的元素个数了，那么就没有必要搜索了。

接下来看一下优化过程如下：

已经选择的元素个数：path.size();
还需要的元素个数为: k - path.size();
在集合n中至多要从该起始位置 : n - (k - path.size()) + 1，开始遍历

为什么有个+1呢，因为包括起始位置，我们要是一个左闭的集合。

举个例子，n = 4，k = 3，目前已经选取的元素为0（path.size为0），n - (k - 0) + 1 即 4 - ( 3 - 0) + 1 = 2。

优化之后的代码：

var combine = function(n, k) {
    const res = []  //结果[][]
    const path = [] //每次递归的结果[]
    // startIndex ：每次递归的起使位置
    const backtracking = (n, k, startIndex)=>{
        if(path.length===k){
            res.push([...path])
            return
        }
        for(let i=startIndex;i<= n-(k-path.length) + 1;i++){	//剪枝优化
            path.push(i)
            backtracking(n,k,i+1)
            path.pop()
        }
    }
    backtracking(n,k,1)
    return res
};

组合 ​

思路 ​

剪枝优化 ​

组合

思路

剪枝优化