无锡营销型网站价格,微信机器人wordpress,展馆设计施工一体化,可以直接进入的正能量网站1 题目
给定一个无重复元素的数组 candidates 和一个目标数 target #xff0c;找出 candidates 中所有可以使数字和为 target 的组合。
candidates 中的数字可以无限制重复被选取。
说明#xff1a;
所有数字#xff08;包括 target#xff09;都是正整数。 解集不能包…1 题目
给定一个无重复元素的数组 candidates 和一个目标数 target 找出 candidates 中所有可以使数字和为 target 的组合。
candidates 中的数字可以无限制重复被选取。
说明
所有数字包括 target都是正整数。 解集不能包含重复的组合。
2 解法
首先要对数组candidates进行遍历, 数组candidates里面的每个元素都有选和不选两种可能, 如果选的话, 剩下的target就是之前的target减去现在这个元素, 根据这种思想, 想到用递归的方法来解这个问题, 且需要进行回溯.
1. 需要维护一个vector, 里面有当前已经选择的元素
2. 因为数组都为互不相同的正整数, 所以如果此时target为0, 那么就直接把当前的vector放入结果中, 返回
3. 如果索引值到达最大值, 也是返回
4. 在选择一个元素完成后, 接下来就是不选这个元素继续进行递归.
代码: void dfs(int target, int index, vectorint candidates, vectorint t_vec, vectorvectorint res_vec) {//target是0, 把当前已经选的元素放进结果里if (target 0) {res_vec.push_back(t_vec);return;}//遍历到头, 返回if (index candidates.size()) {return;}//不选直接跳过dfs(target, index 1, candidates, t_vec, res_vec);//选if (target candidates[index]) {t_vec.push_back(candidates[index]);dfs(target - candidates[index], index, candidates, t_vec, res_vec);//此时最后一个元素就是刚才选的元素, 把他删除掉t_vec.pop_back();}}vectorvectorint combinationSum(vectorint candidates, int target) {vectorvectorint res_vec;vectorint t_vec;dfs(target, 0, candidates, t_vec, res_vec);return res_vec;}
