力扣-77-组合

直达链接

这个问题应该就是我想找的答案了，把k=1~n全部输出一遍
然后如果k=n，那就是全排列问题不对，还是不一样，这里只考虑数字组合，而没考虑数字顺序也就是排列问题

两种解法，第一种是枚举（选和不选两种情况），而且听说可以写for和不写两种写法（有待验证）

而方法二还是采用类似于子序列的生成01序列然后匹配的做法

2022-12-7重做

使用回溯的是全排列，这个不太一样，这个是组合

评论区提醒是：同样可以用回溯，只不过排列每次都是从头开始，需要记录已经访问过的元素，而组合不需要，组合只需要在本次选择后面的元素中进行下一次选择

由这个朴素的思路，写出的代码：

class Solution {
public:
	vector<vector<int>> res;

	void backTrace(vector<int>& temp, int n, int k, int index) {
		if (temp.size() == k) {
			res.push_back(temp);
			return;
		}
                // 这里不要刻意控制右边界
		for (int i = index; i <= n; i++) {
			temp.push_back(i);
			backTrace(temp, n, k, i + 1);
			temp.pop_back();
		}
	}
	vector<vector<int>> combine(int n, int k) {
		vector<int> temp;
		backTrace(temp, n, k, 1);
		return res;
	}
};

去比对了一下两个月前的的代码，有两点注意：

1. 做了一个剪枝，这个剪枝的效果有多大？大概是if (temp.size() + n - index + 1 < k) return;就是我之前想要通过控制右边界却错了做法的想法
2. temp能定义为类变量吗？可以

效果出乎意料的显著，是幻觉吗？！

class Solution {
public:
	vector<vector<int>> res;
	vector<int>temp;

	void backTrace(int n, int k, int index) {
		if (temp.size() + n - index + 1 < k) return;
		if (temp.size() == k) {
			res.push_back(temp);
			return;
		}
		for (int i = index; i <= n; i++) {
			temp.push_back(i);
			backTrace(n, k, i + 1);
			temp.pop_back();
		}
	}
	vector<vector<int>> combine(int n, int k) {
		backTrace(n, k, 1);
		return res;
	}
};