每天一题LeetCode【第31天】(悄悄回来☺️)

T40. Combination Sum II【Medium】

前言

<(￣︶￣)>悄悄回来写 leetcode 。

题目

给定一组候选数（C）和目标数（T），找到 C 中的所有的独特的组合，使得这些候选数之和为 T。

从 C 中选出的数只能用一次。

注意：

• 所有数字（包括目标数）都是是正整数。
• 解集必须不包含重复的组合。

例如，给出的候选数集是 [10, 1, 2, 7, 6, 1, 5] 目标数是 8，

一个解集是：

[
  [1, 7],
  [1, 2, 5],
  [2, 6],
  [1, 1, 6]
]

思路

这题和前面那题非常像，代码也只有总共两点不一样,看过前面的人可以跳过直接看补充。

这题这里用了递归，用的是非代码状态下的正常思路，从左往右选一个数然后往后找数（不包括自己），看看能不凑出来一个和为 T 的数。这个过程中 target 不断变化:

target = 原目标数 - 选好的数（cur 数组中的数）之和

若 target = 0 时，则代表找到了正确的组合，于是把正确的组合（cur）加入 result，并中断这一层的递归。

代码

代码取自 Top Solution，稍作注释

 public class Solution {
 public List<List<Integer>> combinationSum2(int[] candidates, int target) {
       //排序
        Arrays.sort(candidates);
        //初始化一个泛型为List<Integer>的List作为返回值类型
        List<List<Integer>> result = new ArrayList<List<Integer>>();
        //调用getResult方法
        getResult(result, new ArrayList<Integer>(), candidates, target, 0);
        return result;
    }
    
    private void getResult(List<List<Integer>> result, List<Integer> cur, int candidates[], int target, int start){
        if(target > 0){
            for(int i = start; i < candidates.length && target >= candidates[i]; i++){
                //如果相等就跳过，解决了重复问题
                if(i > start && candidates[i] == candidates[i-1]) continue; 
               //这里用了递归，用的是非代码状态下的正常思路，从左往右选一个数
               //然后往后找数（不包括自己），看看能不凑出来一个和为 T 的数
                cur.add(candidates[i]);
                //target = 原目标数 - 选好的数（cur 数组中的数）之和
                getResult(result, cur, candidates, target - candidates[i], i+1);//这里i+1,保证自己不重复加
                cur.remove(cur.size() - 1);
            }
        }
        //当递归中 target 等于 0 的时候代表了找到了这个数，那就把 cur 加入result就好，并且中断这一层递归
        else if(target == 0 ){
            result.add(new ArrayList<Integer>(cur));
        }//else if
    }
}

补充

这题和前面那题非常像，代码也只有总共两点不一样。

① 因为给出的数组里面有重复的了，用下面这句话来排除用同样的一个数造成的重复结果。
如果不处理当选数集 [10, 1, 2, 7, 6, 1, 5] 目标数是 8 时，会出现[1,7], [7,1]两次

 if(i > start && candidates[i] == candidates[i-1]) continue;

② 因为题中说每个数只能用一次，自己不能重复用了，所以把最后一个参数应该变成 i+1 不能把自己算进去了

 getResult(result, cur, candidates, target - candidates[i], i+1);