leetcode40-组合总和II

原题

给定一个数组 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]
]

解法

思想

这道题和leetcode39-组合总和的区别是,数组中的每个数字只能使用一次,并且数组中可能存在相同的数字。

该题要求反映到搜索树中,就是不允许同层出现相同的数字,而允许上下层之间存在相同的数字。

我们使用上道题的代码进行改造,如下所示:

代码

class Solution {
    List<List<Integer>> ans;
    int[] candidates;
    public List<List<Integer>> combinationSum2(int[] candidates, int target) {
        ans = new ArrayList<>();
        Arrays.sort(candidates);
        this.candidates = candidates;
        List<Integer> list = new ArrayList<>();
        dfs(list,target,0);
        return ans;
    }

    public void dfs(List<Integer> list,int target,int minIndex){
        for(int i = minIndex;i<candidates.length;i++){
            //如果当前元素等于上一元素,则跳过(不允许同层出现相同的数字)
            if(i!=minIndex && candidates[i] == candidates[i-1]) continue;
            if(candidates[i]<=target){
                List<Integer> copyList = new ArrayList<>(list);
                copyList.add(candidates[i]);
                if(candidates[i]==target) {
                    ans.add(copyList);
                    return;
                }
                //允许搜索的最小的下标加一(允许上下层之间存在相同的数字)
                dfs(copyList,target-candidates[i],i+1);
            }
        }
    }
}

原创文章,作者:彭晨涛,如若转载,请注明出处:https://www.codetool.top/article/leetcode40-%e7%bb%84%e5%90%88%e6%80%bb%e5%92%8cii/

发表评论

电子邮件地址不会被公开。