企业网站推广策略,网站营销方案模板,网站流量检测,做影视网站代理犯法吗1. 题目链接#xff1a;39. 组合总和
2. 题目描述#xff1a; 给你一个 无重复元素 的整数数组 candidates 和一个目标整数 target #xff0c;找出 candidates 中可以使数字和为目标数 target 的 所有 不同组合 #xff0c;并以列表形式返回。你可以按 任意顺序 返回这些…1. 题目链接39. 组合总和
2. 题目描述 给你一个 无重复元素 的整数数组 candidates 和一个目标整数 target 找出 candidates 中可以使数字和为目标数 target 的 所有 不同组合 并以列表形式返回。你可以按 任意顺序 返回这些组合。 candidates 中的 同一个 数字可以 无限制重复被选取 。如果至少一个数字的被选数量不同则两种组合是不同的。 对于给定的输入保证和为 target 的不同组合数少于 150 个。 示例 1 输入candidates [2,3,6,7], target 7
输出[[2,2,3],[7]]
解释
2 和 3 可以形成一组候选2 2 3 7 。注意 2 可以使用多次。
7 也是一个候选 7 7 。
仅有这两种组合。示例 2 输入: candidates [2,3,5], target 8
输出: [[2,2,2,2],[2,3,3],[3,5]]示例 3 输入: candidates [2], target 1
输出: []提示 1 candidates.length 302 candidates[i] 40candidates 的所有元素 互不相同1 target 40 3. 解法
3.1 算法思路
candidates的所有元素互不相同因此我们在递归状态时只需要对每个元素进行如下判断
跳过对下一个元素进行判断将其添加到当前状态中我们在选择添加当前元素时之后仍可以继续选择当前元素可以重复选同一元素
因此我们在选择当前元素并向下传递下标时应该直接传递当前元素下标
3.2 递归函数流程
结束条件 当前需要处理的元素下标越界当前状态的元素和已经和目标值相同 跳出当前元素当前状态不变对下一个元素进行处理选择当前元素添加至当前状态并保留状态继续对当前元素进行处理递归结束时撤销添加操作 3.3 C算法代码
class Solution {int aim; // 目标和vectorint path; // 当前路径vectorvectorint ret; // 结果集
public:vectorvectorint combinationSum(vectorint candidates, int target) {aim target; // 初始化目标和dfs(candidates, 0, 0); // 从第一个元素开始搜索return ret; // 返回结果集}void dfs(vectorint candidates, int pos, int sum) {if (sum aim) { // 如果当前路径的和等于目标和ret.push_back(path); // 将当前路径加入结果集return; // 结束当前递归}if (sum aim || pos candidates.size()) { // 如果当前路径的和大于目标和或者已经遍历完所有元素return; // 结束当前递归}for (int k 0; k * candidates[pos] sum aim; k) { // 遍历当前元素的所有可能组合if (k) path.push_back(candidates[pos]); // 如果当前元素被使用将其加入当前路径dfs(candidates, pos 1, sum k * candidates[pos]); // 继续搜索下一个元素}for (int k 1; k * candidates[pos] sum aim; k) { // 回溯移除当前元素path.pop_back();}}
};
