【回溯】组合

回溯三部曲

1. 返回值及参数定义
2. 终止条件
3. 搜索过程
   题目：实现123可能出现的组合

class SolutionCombination{
public:
	vector<int> tmp;
	vector<vector<int>> ans;
public:
	void dfs(vector<int>& nums, int k, int idx) {
		if (tmp.size() == k){
			ans.emplace_back(tmp);
			return ;
		}
		for(int i=idx;i<nums.size();++i) {
		// 优化 i的条件，从而减至
		// for(int i=idx;i
			tmp.emplace_back(nums[i]);
			dfs(nums, k, i+1);
			tmp.pop_back();
		}
	}
	vector<vector<int>> combine(vector<int>& nums, int k){
		dfs(nums, 2, 0);
		return ans;
	}
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23

递归过程，图示：