77-组合(回溯算法)

题目

给定两个整数 n 和 k，返回范围 [1, n] 中所有可能的 k 个数的组合。
你可以按任何顺序返回答案。
示例 1：
输入：n = 4, k = 2
输出：
[
[2,4],
[3,4],
[2,3],
[1,2],
[1,3],
[1,4],
]
示例 2：
输入：n = 1, k = 1
输出：[[1]]
提示：
1 <= n <= 20
1 <= k <= n

分析

子集和组合类问题与排列不同,不受顺序影响.所以需要防止重复.
我们通过保证元素之间的相对顺序不变来防止出现重复的子集。具体方法就是用start标记,下一次只能选取后面的元素.
算法框架:

路径列表
路径
void backtrack(选择列表) {
	if 路径 合格:
		路径列表.add(路径)
		// return 因为子集还能生长,如果需要增长就提前结束
	for 选择 in 选择列表[start:]:
		if 选择 不合格:
			continue //进行下一个选择
		路径.add(选择)
		backtrack(选择列表,start+1)
		路径.pop(选择) //重新进行下一个选择
}

C++代码

class Solution {
private:
    vector<int> _trace;
    vector<vector<int>> _results;
    void backtrack(const int& n, const int& k, const int start){
        if(_trace.size()==k){
            _results.push_back(_trace);
            return;//提取终止当前树枝
        }
        for(int i=start; i<=n; i++){
            _trace.push_back(i);
            backtrack(n,k,i+1);
            _trace.pop_back();
        }
    }
public:
    vector<vector<int>> combine(int n, int k) {
        backtrack(n, k, 1);
        return _results;
    }
};

试一下让start作为成员变量会怎么样

class Solution {
private:
    vector<int> _trace;
    vector<vector<int>> _results;
    int _start;
    void backtrack(const int& n, const int& k){
        if(_trace.size()==k){
            _results.push_back(_trace);
            return;//提取终止当前树枝
        }
        for(int i=_start; i<=n; i++){
            _trace.push_back(i);
            int tem = _start;
            _start = i+1;
            backtrack(n,k);
            _trace.pop_back();
            _start = tem;
        }
    }
public:
    vector<vector<int>> combine(int n, int k) {
        _start=1;
        backtrack(n, k);
        return _results;
    }
};