[数据结构与算法]LeetCode 39.组合总和 (搜索回溯 C/C++)

题目链接

//方法一：搜索回溯
class Solution {
public:
	void dfs(vector<int>& candidates,int target,vector<vector<int>>& ans,
		vector<int>& combine,int idx) {
		//递归终止条件
		if(idx==candidates.size())return;
		if(target==0) {
			ans.push_back(combine);
			return ;
		}
		//直接跳过当前索引对应的值
		dfs(candidates,target,ans,combine,idx+1);
		//选择当前索引对应的值
		if(target-candidates[idx]>=0) {
			combine.push_back(candidates[idx]);
			//然后继续从当前位置开始搜索
			dfs(candidates,target-candidates[idx],ans,combine,idx);
			//搜索完毕后将刚才插入的值删除
			combine.pop_back();
		}

	}

	vector<vector<int>> combinationSum(vector<int> candidates,int target) {
		vector<vector<int>> ans;
		vector<int> combine;
		dfs(candidates,target,ans,combine,0);
		return ans;
	}


};