# 题目

给定两个整数 n 和 k，返回 1 ... n 中所有可能的 k 个数的组合。

示例：输入: n = 4, k = 2 输出: [[2,4], [3,4], [2,3], [1,2], [1,3], [1,4], ]

77. 组合 - 力扣（LeetCode）

# 分析

把题目抽象成树状图

深度为 k 的 n 叉树

回溯三部曲：

1 递归函数的参数和返回值

这里需要两个全局变量，一个存放单一结果，另一个存放符合条件的结果集合，初次之外还需要一个 int 型变量来记录本层递归的起点

	vector<vector<int>> result; // 存放符合条件结果的集合
	vector<int> path; // 用来存放符合条件结果
	void backtracking(int n, int k, int startIndex)

2 回溯的终止条件

当 path 数组大小到 k 时说明已经到叶子节点了

3 单层搜索过程

	for (int i = startIndex; i <= n; i++) { // 控制树的横向遍历
	path.push_back(i); // 处理节点
	backtracking(n, k, i + 1); // 递归：控制树的纵向遍历，注意下一层搜索要从 i+1 开始
	path.pop_back(); // 回溯，撤销处理的节点
	}

完整代码

	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;
	}
	};

剪枝优化：

	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;
	}
	};

回溯