https://leetcode.cn/problems/combinations/description/

<aside> 💡

回溯三部曲：

• 参数：
  • vector<vector<int>> ans：存放最终结果的数组（全局变量）
  • vector<int> cur：当前路径下的组合（全局变量）
  • int num：当前已经完成搜索的值，本次递归中从num + 1开始搜索
  • int& k，int& n：题意中的k与n
• 终止条件：组合中的元素个数等于k，说明完成组合，将结果进行保存并返回
• 单层逻辑：
  • 节点操作：当前组合（cur）中添加当前值（i）
  • 递归：i已经完成操作，传入i+1进行递归
  • 回溯：i在该位置的所有组合已经收集完成，将i弹出当前组合 </aside>

vector<int> cur;
vector<vector<int>> ans;

void backtracking(int i, int n, int k) {
    if (cur.size() == k) {
        ans.push_back(cur);
        return;
    }

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

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

<aside> 💡

进阶：剪枝：

原循环终止条件：i <= n;

• 剪枝后的终止条件： i <= n - (k - cur.size()) + 1
• 剪枝条件即：n - i + 1 >= k - size
• n - i + 1代表当前序列中还剩下的元素个数（+1代表包括了当前节点）
  • k - size代表组合中还需要几个元素
  • 故整个剪枝的含义为：当前序列中剩余的元素需要大于等于组合中还缺的元素个数 </aside>

vector<vector<int>> ans;
vector<int> cur;

void backtracking(int num, int& k, int& n) {
		// 终止条件：数组长度为k
		if (cur.size() == k) {
				// 保存结果
				ans.push_back(cur);
				return;
		}
	
		for (int i = num + 1; i <= n - (k - cur.size()) + 1; ++i) {
				// 进行节点操作
				cur.push_back(i);
				// 递归
				backtracking(i, k, n);
				// 还原节点操作（回溯）
				cur.pop_back();
		}
}

vector<vector<int>> combine(int n, int k) { 
		backtracking(0, k, n);
		return ans;
}