做搞笑图片的网站网站设计深圳

当前位置： 首页 > news >正文

做搞笑图片的网站,网站设计深圳,整站网站优化,网站建设投标书39. 组合总和 39. 组合总和 - 力扣#xff08;LeetCode#xff09;https://leetcode.cn/problems/combination-sum/description/ 题目描述#xff1a; 给你一个 无重复元素 的整数数组 candidates 和一个目标整数 target #xff0c;找出 candidates 中可以使数字和为目标数… 39. 组合总和 39. 组合总和 - 力扣LeetCodehttps://leetcode.cn/problems/combination-sum/description/ 题目描述 给你一个 无重复元素 的整数数组 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 思路分析 由于所有candidates的数1所以不必担心有0的问题。另外由于元素可以多次使用所以其搜索过程对应的树形结构如下所示 注意图中叶子节点的返回条件因为本题没有组合数量要求仅仅是总和的限制所以递归没有层数的限制只要选取的元素总和超过target就返回 另外注意蓝色框中文字因为要求的是满足条件的 下面我们结合上述的树形结构图按照回溯三部曲来尝试书写代码 回溯第一步确认回溯函数的参数和返回值。 这里依然是定义两个全局变量二维数组result存放结果集数组path存放符合条件的结果。这两个变量可以作为函数参数传入  老规矩返回值类型void。参数除了题目所给的数组candidates以及目标和target之外为了方便理解我们算法练习第21天|216.组合总和|||、17.电话号码的字母组合-CSDN博客中的216.组合总和|||的解法一样添加了目前路径上所遍历的元素的和sum以及开始遍历的位置startIndex。 可能有人有人会有疑问为什么在17.电话号码的字母组合这一题中没有写startIndex对于组合问题什么时候需要startIndex呢下面给出startIndex的使用场景 如果是从一个集合中求组合的话就需要startIndex例如算法练习第20天|回溯算法 77.组合问题 257. 二叉树的所有路径-CSDN博客中的77.组合问题以及上述的216.组合总和|||。 如果是多个集合取组合各个集合之间相互不影响那么就不用startIndex例如上面的17.电话号码的字母组合。 所以本题要求是从同一个集合中求组合所以要用到startIndex。至于具体怎么用下面代码中在细说。 回溯函数大致长这样 vectorvectorint result; vectorint path; //回溯第一步确定回溯函数的参数和返回类型 void backTracking(vectorint candidates, int target, int sum, int startIndex){} 回溯函数第二步确认回溯终止条件  从下面的树形结构可知 回溯的终止条件只有 sum targeth和sum target两种。如果是sumtarget则说明还有继续寻找并添加元素的可能所以这种要执行的是单层回溯的逻辑。 所以回溯终止条件长这样 //回溯第二步确定回溯终止条件 if(sum target){result.push_back(path);return; } else if(sum target){return; } 回溯第三步确认单层搜索逻辑 能到达这一步表明sumtarget需要继续进行元素搜索。因此要做的操作有处理节点sum加上当前节点path中记录当前节点然后就该执行递归了接着是回溯。代码如下: //回溯第三步确认当层回溯逻辑并回溯 for(int i startIndex; i candidates.size(); i){sum candidates[i]; //处理节点path.push_back(candidates[i]);backTracking(candidates, target, sum, i); //递归sum - candidates[i]; //回溯path.pop_back();} 这里我们用到了startIndex注意我们在递归时的给最后一个参数传的是i程序初始时传的startIndex肯定为0所以i最开始为0。但是搜索完最左侧的大分支后该记录的结果记录下来该回溯的回溯i变成了1结合下图为了避免上面所说的【23】和【32】的组合重复所以取数时变成了从【35】中取数这就导致startIndex也需要有更新。那么更新为多少时何时呢观察下图可知当startIndex和此时的i一样时就满足了从【35】中取数的条件于是我们在递归时把i作为了第四个参数的实参。 整体代码 整体代码的书写如下 class Solution { public:vectorvectorint result;vectorint path;//回溯第一步确定回溯函数的参数和返回类型void backTracking(vectorint candidates, int target, int sum, int startIndex){//回溯第二步确定回溯终止条件if(sum target){result.push_back(path);return;}else if(sum target){return;}//回溯第三步确认当层回溯逻辑并回溯for(int i startIndex; i candidates.size(); i){sum candidates[i]; //处理节点path.push_back(candidates[i]);backTracking(candidates, target, sum, i); //递归sum - candidates[i]; //回溯path.pop_back();}}vectorvectorint combinationSum(vectorint candidates, int target) {backTracking(candidates,target,0,0);return result; } }; 40.组合总和II  40. 组合总和 II - 力扣LeetCodehttps://leetcode.cn/problems/combination-sum-ii/description/ 题目描述: 给定一个候选人编号的集合 candidates 和一个目标数 target 找出 candidates 中所有可以使数字和为 target 的组合。 candidates 中的每个数字在每个组合中只能使用 一次 。 注意解集不能包含重复的组合。  示例 1: 输入: candidates  [10,1,2,7,6,1,5] target  8输出: [ [1,1,6], [1,2,5], [1,7], [2,6] ] 示例 2: 输入: candidates  [2,5,2,1,2], target  5, 输出: [ [1,2,2], [5] ]提示: 1  candidates.length 1001  candidates[i] 501 target 30 本人看完解法也不太理解哎先放着。。。。 class Solution { private:vectorvectorint result;vectorint path;void backtracking(vectorint candidates, int target, int sum, int startIndex, vectorbool used) {if (sum target) {result.push_back(path);return;}for (int i startIndex; i candidates.size() sum candidates[i] target; i) {// used[i - 1] true说明同一树枝candidates[i - 1]使用过// used[i - 1] false说明同一树层candidates[i - 1]使用过// 要对同一树层使用过的元素进行跳过if (i 0 candidates[i] candidates[i - 1] used[i - 1] false) {continue;}sum candidates[i];path.push_back(candidates[i]);used[i] true;backtracking(candidates, target, sum, i 1, used); // 和39.组合总和的区别1这里是i1每个数字在每个组合中只能使用一次used[i] false;sum - candidates[i];path.pop_back();}}public:vectorvectorint combinationSum2(vectorint candidates, int target) {vectorbool used(candidates.size(), false);path.clear();result.clear();// 首先把给candidates排序让其相同的元素都挨在一起。sort(candidates.begin(), candidates.end());backtracking(candidates, target, 0, 0, used);return result;} };