LeetCode-40.组合总和II

骑猪看日落 2022-01-25 22:35 227阅读 0赞

# 题目 #

给定一个数组 candidates 和一个目标数 target ，找出 candidates 中所有可以使数字和为 target 的组合。

**candidates 中的每个数字在每个组合中只能使用一次。**

说明：  
**所有数字（包括目标数）都是正整数。  
解集不能包含重复的组合。**

###### 示例 1: ######

> 输入: candidates = \[10,1,2,7,6,1,5\], target = 8  
> 所求解集为: \[ \[1, 7\], \[1, 2, 5\], \[2, 6\], \[1, 1, 6\] \]

###### 示例 2: ######

> 输入: candidates = \[2,5,2,1,2\], target = 5  
> 所求解集为: \[ \[1,2,2\], \[5\] \]

解题思路—**回溯法**：**这一题是回溯法的经典应用，是[LeetCode-39.组合总和][LeetCode-39.]的衍生题**，其中的区别就是能否重复使用candidates中的数值。**如果每个数值只能使用一次，需要在递归时判断当前数字之前有没有出现过。**

## Java解题—回溯法 ##

import java.util.ArrayList;
    import java.util.List;
    class Solution {
        public List<List<Integer>> res = new ArrayList<>();
        public List<List<Integer>> combinationSum2(int[] candidates, int target) {
            if(target==0) return res;
            List<Integer> list = new ArrayList<>();
            Arrays.sort(candidates);
            addSum(candidates, target, list, 0, 0);
            return res;
        }
        
        public void addSum(int[] candidates, int target, List<Integer> list, int sum, int index){
            if(sum>target) return;
            if(sum==target){
                res.add(list);
                return;
            }
    
            for(int i=index;i<candidates.length && candidates[i]<=target;i++){
                if(i!=index && candidates[i]==candidates[i-1])
                    continue;
                List<Integer> curlist = new ArrayList<>(list);
                curlist.add(candidates[i]);
                addSum(candidates, target, curlist, sum+candidates[i], i+1);
            }
        }
    }

[LeetCode-39.]: https://blog.csdn.net/gaoyueace/article/details/90599437