力扣算法ing(57 / 100)

4.15 39.组合总和

给你一个 无重复元素 的整数数组 candidates 和一个目标整数 target ，找出 candidates 中可以使数字和为目标数 target 的 所有 不同组合 ，并以列表形式返回。你可以按 任意顺序 返回这些组合。
candidates 中的 同一个 数字可以 无穷制重复被选取 。如果至少一个数字的被选数量不同，则两种组合是不同的。
对于给定的输入，保证和为 target 的不同组合数少于 150 个。
示例 1：

1. 输入：candidates = [2,3,6,7], target = 7
2. 输出：[[2,2,3],[7]]
3. 解释：
4. 2 和 3 可以形成一组候选，2 + 2 + 3 = 7 。注意 2 可以使用多次。
5. 7 也是一个候选， 7 = 7 。
6. 仅有这两种组合。

复制代码

示例 2：

1. 输入: candidates = [2,3,5], target = 8
2. 输出: [[2,2,2,2],[2,3,3],[3,5]]

复制代码

示例 3：

1. 输入: candidates = [2], target = 1
2. 输出: []

复制代码

我的思路：
找出 candidates 中可以使数字和为目标数 target 的 所有 不同组合 并以列表形式返回。
它可以是重复的
不须要startIndex,每次都从数组[0]开始遍历
但是答案错误啦！处置惩罚相同的排序应该怎么办,通过index进行去重
2 3 5
235 35 5

1. sum += candidates[i];
2.              if(sum > target ){
3.                 break;
4.             }

复制代码

如果是这样当sum>tartget的时候直接break了，i+1，又继续 sum += candidates;
就会导致sum一直比startget大
我的代码：

2. function combinationSum(candidates: number[], target: number): number[][] {
3.     const path = [];//存储每一次递归树的
4.     const res = [];//存储答案
5.     function backtracking(sum : number , startIndex:number){
6.         if(sum === target){
7.             res.push([...path]);
8.             return;
9.         }
10.         for(let i = startIndex ; i < candidates.length ; i++){
11.             sum += candidates[i];
12.              if(sum > target ){
13.             sum -= candidates[i]; // 回溯sum
14.             break;
15.             }
16.             path.push(candidates[i]);
17.             backtracking(sum , i);//因为可以使用重复的数字，所以是i
18.             sum -= candidates[i];
19.             path.pop();
20.         }
21.     }
22.     backtracking(0 , 0);
23.     return res;
24.    
25. };

复制代码

解答错误：使用 break 会导致循环提前终止，而您想要的是在 sum 超过 target 时继续尝试下一个候选数字。因此，应该使用 continue 而不是 break。
终极代码：

1. function combinationSum(candidates: number[], target: number): number[][] {
2.     const path = [];//存储每一次递归树的
3.     const res = [];//存储答案
4.     function backtracking(sum : number , startIndex:number){
5.         if(sum === target){
6.             res.push([...path]);
7.             return;
8.         }
9.         for(let i = startIndex ; i < candidates.length ; i++){
10.             sum += candidates[i];
11.              if(sum > target ){
12.             sum -= candidates[i]; // 回溯sum
13.             continue;
14.             }
15.             path.push(candidates[i]);
16.             backtracking(sum , i);//因为可以使用重复的数字，所以是i
17.             sum -= candidates[i];
18.             path.pop();
19.         }
20.     }
21.     backtracking(0 , 0);
22.     return res;
23.    
24. };

复制代码

总结：这一道题目我看到允许重复就直接for循环从i=0，开始的但是我还是忽略了[2,3,3][3,2,3]实在是一样的。在之前我们的startIndex=i+1,这里我们只须要startIndex=i就可以啦!在处置惩罚sum>target的时候也要注意，由于我们>之后还要继续循环其他的数字，所以不是break,别的我们还要还原sum

免责声明：如果侵犯了您的权益，请联系站长，我们会及时删除侵权内容，谢谢合作！更多信息从访问主页：qidao123.com:ToB企服之家，中国第一个企服评测及商务社交产业平台。