欢迎大家参与本项目，贡献其他语言版本的代码，拥抱开源，让更多学习算法的小伙伴们收益！

在回溯算法：求组合问题！中，我们通过回溯搜索法，解决了n个数中求k个数的组合问题。

可以直接看我的B栈视频讲解：带你学透回溯算法-组合问题的剪枝操作

文中的回溯法是可以剪枝优化的，本篇我们继续来看一下题目77. 组合。

链接：https://leetcode-cn.com/problems/combinations/

大家先回忆一下[77. 组合]给出的回溯法的代码：

class Solution {
private:
    vector<vector<int>> result; // 存放符合条件结果的集合
    vector<int> path; // 用来存放符合条件结果
    void backtracking(int n, int k, int startIndex) {
        if (path.size() == k) {
            result.push_back(path);
            return;
        }
        for (int i = startIndex; i <= n; i++) {
            path.push_back(i); // 处理节点
            backtracking(n, k, i + 1); // 递归
            path.pop_back(); // 回溯，撤销处理的节点
        }
    }
public:
    vector<vector<int>> combine(int n, int k) {
        result.clear(); // 可以不写
        path.clear();   // 可以不写
        backtracking(n, k, 1);
        return result;
    }
};

剪枝优化

我们说过，回溯法虽然是暴力搜索，但也有时候可以有点剪枝优化一下的。

在遍历的过程中有如下代码：

for (int i = startIndex; i <= n; i++) {
    path.push_back(i);
    backtracking(n, k, i + 1);
    path.pop_back();
}

这个遍历的范围是可以剪枝优化的，怎么优化呢？

来举一个例子，n = 4，k = 4的话，那么第一层for循环的时候，从元素2开始的遍历都没有意义了。在第二层for循环，从元素3开始的遍历都没有意义了。

这么说有点抽象，如图所示：

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

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

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

注意代码中i，就是for循环里选择的起始位置。

for (int i = startIndex; i <= n; i++) {

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

已经选择的元素个数：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。

从2开始搜索都是合理的，可以是组合[2, 3, 4]。

这里大家想不懂的话，建议也举一个例子，就知道是不是要+1了。

所以优化之后的for循环是：

for (int i = startIndex; i <= n - (k - path.size()) + 1; i++) // i为本次搜索的起始位置

优化后整体代码如下：

class Solution {
private:
    vector<vector<int>> result;
    vector<int> path;
    void backtracking(int n, int k, int startIndex) {
        if (path.size() == k) {
            result.push_back(path);
            return;
        }
        for (int i = startIndex; i <= n - (k - path.size()) + 1; i++) { // 优化的地方
            path.push_back(i); // 处理节点
            backtracking(n, k, i + 1);
            path.pop_back(); // 回溯，撤销处理的节点
        }
    }
public:

    vector<vector<int>> combine(int n, int k) {
        backtracking(n, k, 1);
        return result;
    }
};

总结

本篇我们准对求组合问题的回溯法代码做了剪枝优化，这个优化如果不画图的话，其实不好理解，也不好讲清楚。

所以我依然是把整个回溯过程抽象为一颗树形结构，然后可以直观的看出，剪枝究竟是剪的哪里。

就酱，学到了就帮Carl转发一下吧，让更多的同学知道这里！

其他语言版本

Java：

class Solution {
    List<List<Integer>> result = new ArrayList<>();
    LinkedList<Integer> path = new LinkedList<>();
    public List<List<Integer>> combine(int n, int k) {
        combineHelper(n, k, 1);
        return result;
    }

    /**
     * 每次从集合中选取元素，可选择的范围随着选择的进行而收缩，调整可选择的范围，就是要靠startIndex
     * @param startIndex 用来记录本层递归的中，集合从哪里开始遍历（集合就是[1,...,n] ）。
     */
    private void combineHelper(int n, int k, int startIndex){
        //终止条件
        if (path.size() == k){
            result.add(new ArrayList<>(path));
            return;
        }
        for (int i = startIndex; i <= n - (k - path.size()) + 1; i++){
            path.add(i);
            combineHelper(n, k, i + 1);
            path.removeLast();
        }
    }
}

Python：

class Solution:
    def combine(self, n: int, k: int) -> List[List[int]]:
        res=[]  #存放符合条件结果的集合
        path=[]  #用来存放符合条件结果
        def backtrack(n,k,startIndex):
            if len(path) == k:
                res.append(path[:])
            return 
            for i in range(startIndex,n-(k-len(path))+2):  #优化的地方
                path.append(i)  #处理节点 
                backtrack(n,k,i+1)  #递归
                path.pop()  #回溯，撤销处理的节点
    backtrack(n,k,1)
    return res

Go：

var res [][]int 
func combine(n int, k int) [][]int {
   res=[][]int{}
   if n <= 0 || k <= 0 || k > n {
		return res
	}
    backtrack(n, k, 1, []int{})
	return res
}
func backtrack(n,k,start int,track []int){
    if len(track)==k{
        temp:=make([]int,k)
        copy(temp,track)
        res=append(res,temp)
    }
    if len(track)+n-start+1 < k {
			return
		}
    for i:=start;i<=n;i++{ 
        track=append(track,i)
        backtrack(n,k,i+1,track)
        track=track[:len(track)-1]
    }
}

javaScript:

var combine = function(n, k) {
    const res = [], path = [];
    backtracking(n, k, 1);
    return res;
    function backtracking (n, k, i){
        const len = path.length;
        if(len === k) {
            res.push(Array.from(path));
            return;
        }
        for(let a = i; a <= n + len - k + 1; a++) {
            path.push(a);
            backtracking(n, k, a + 1);
            path.pop();
        }
    }
};

C:

int* path;
int pathTop;
int** ans;
int ansTop;

void backtracking(int n, int k,int startIndex) {
    //当path中元素个数为k个时，我们需要将path数组放入ans二维数组中
    if(pathTop == k) {
        //path数组为我们动态申请，若直接将其地址放入二维数组，path数组中的值会随着我们回溯而逐渐变化
        //因此创建新的数组存储path中的值
        int* temp = (int*)malloc(sizeof(int) * k);
        int i;
        for(i = 0; i < k; i++) {
            temp[i] = path[i];
        }
        ans[ansTop++] = temp;
        return ;
    }

    int j;
    for(j = startIndex; j <= n- (k - pathTop) + 1;j++) {
        //将当前结点放入path数组
        path[pathTop++] = j;
        //进行递归
        backtracking(n, k, j + 1);
        //进行回溯，将数组最上层结点弹出
        pathTop--;
    }
}

int** combine(int n, int k, int* returnSize, int** returnColumnSizes){
    //path数组存储符合条件的结果
    path = (int*)malloc(sizeof(int) * k);
    //ans二维数组存储符合条件的结果数组的集合。（数组足够大，避免极端情况）
    ans = (int**)malloc(sizeof(int*) * 10000);
    pathTop = ansTop = 0;

    //回溯算法
    backtracking(n, k, 1);
    //最后的返回大小为ans数组大小
    *returnSize = ansTop;
    //returnColumnSizes数组存储ans二维数组对应下标中一维数组的长度（都为k）
    *returnColumnSizes = (int*)malloc(sizeof(int) *(*returnSize));
    int i;
    for(i = 0; i < *returnSize; i++) {
        (*returnColumnSizes)[i] = k;
    }
    //返回ans二维数组
    return ans;
}

作者微信：程序员Carl
B站视频：代码随想录
知识星球：代码随想录

Provide feedback

Saved searches

Use saved searches to filter your results more quickly

0077.组合优化.md

0077.组合优化.md

剪枝优化

总结

其他语言版本

Files

0077.组合优化.md

Latest commit

History

0077.组合优化.md

File metadata and controls

剪枝优化

总结

其他语言版本