// 回溯模板
void backtracking(参数){
    if (终止条件){
        存放结果;
        return;
    }
    
    for( 选择：本层集合中元素（树中节点孩子的数量就是集合的大小）){
        处理节点;
        backtracking(路径,选择列表); // 递归
        回溯，撤销处理结果
    }
}

#include <iostream>
#include <vector>
using namespace std;
class Solution {
public:
	vector<int> path;	//存储每个可能结果
	vector<vector<int>> result;	//存储最终结果
	void backtracking(int n, int k, int startIndex) {
		// 确定终止条件 path长度达到n就终止
		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();	//弹出元素 回溯
		}	
	}
	vector<vector<int>> combine(int k, int n) {
		int i = 1;
		backtracking(n, k, i);
		return result;
	}
};

int main() {

	Solution solution;
	int k=2;
	int n=4;
	//int startIndex;
	//cin >> k;	//输入k
	//cin >> n;	//组合长度
	//cin >> startIndex; //输入startIndex
	vector<vector<int>> test = solution.combine(k,n);
	cout << test.size() << endl;
	for (int i = 0; i < test.size(); i++) {
		for (int j = 0; j < k; j++) {
			cout << test[i][j] << ' ';
		}
		cout << endl;
	}
	return 0;
}

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