如何自己创办一个网站,工商银行建设银行招商银行网站,试玩网站开发,静态网站模板源码下载习题#xff1a;#xff08;leetcode39#xff09;
给你一个 无重复元素 的整数数组 candidates 和一个目标整数 target #xff0c;找出 candidates 中可以使数字和为目标数 target 的 所有 不同组合 #xff0c;并以列表形式返回。你可以按 任意顺序 返回这些组合。
c…习题leetcode39
给你一个 无重复元素 的整数数组 candidates 和一个目标整数 target 找出 candidates 中可以使数字和为目标数 target 的 所有 不同组合 并以列表形式返回。你可以按 任意顺序 返回这些组合。
candidates 中的 同一个 数字可以 无限制重复被选取 。如果至少一个数字的被选数量不同则两种组合是不同的。
对于给定的输入保证和为 target 的不同组合数少于 150 个。
分析
回溯三部曲
1.回溯函数模版返回值以及参数
2.回溯函数终止条件
3.回溯搜索的遍历过程
回溯伪代码:
void backtracking(参数){if(终止条件){存放结果;return;}
for(选择本层集合中元素){处理节点;backtracking(路径选择列表);//就是遍历下一层回溯撤销处理结果;}
}
使用的方法是回溯还是遍历整体得到答案但此题不同题目中说可以有重复的元素此时就要考虑回溯函数中的参数如何写。可能大家也想到能不能通过创建used数组来记录元素使用情况如果在不满足target的情况下让原元素仍可继续使用。但这种方法还是太麻烦。此题的巧妙之处就是在回溯函数中的参数如何满足题目条件。就是在定义的index在传递时传的是当前的遍历的值即就是indexi传i的值。backtracking(candidates, target, sum, i);就是本题的关键其余代码根据回溯三步曲和回溯模板就可以写出。
代码分析
class Solution {
public:// 存储所有可能的组合结果vectorvectorint result;// 存储当前正在构建的组合vectorint path;// 回溯函数用于找到所有可能的组合void backtracking(vectorint candidates, int target, int sum, int index) {// 如果当前组合的和超过了目标值则直接返回if (sum target) return;// 如果当前组合的和等于目标值则将当前组合添加到结果集中if (sum target) {result.push_back(path);return;}// 遍历候选数字从index开始允许重复使用数字for (int i index; i candidates.size(); i) {// 将当前候选数字加入当前组合并更新当前组合的和sum candidates[i];path.push_back(candidates[i]);// 递归调用回溯函数由于可以重复使用数字所以index仍然是ibacktracking(candidates, target, sum, i);// 回溯移除最后加入的数字并恢复之前的和sum - candidates[i];path.pop_back();}}vectorvectorint combinationSum(vectorint candidates, int target) {backtracking(candidates, target, 0, 0);return result;}
};
