组合总和2（中等题）

2020-09-12

40. 组合总和 II

难度中等516收藏分享切换为英文接收动态反馈

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

暴力解法

class Solution {
    private List<List<Integer>> ans=new ArrayList<>();
    public List<List<Integer>> combinationSum2(int[] candidates, int target) {
        List<Integer> tempList=new ArrayList<>();
        List<Integer> indexList=new ArrayList<>();//保存的下标去重的临时下标
        Arrays.sort(candidates);
        boolean[] flags=new boolean[candidates.length];//去重标识
        calc(candidates, target,flags,tempList,indexList,0);
        return ans;
    }

    public Integer calc(int[] candidates, int target,boolean[] flags, List<Integer> tempList,List<Integer> indexList,int start){

        int sum=0;
        for(Integer val:tempList){
            sum+=val;
        }

        if(sum>=target){//如果和已经大于或等于，没必要继续添加其他数字进来
            return sum;
        }

        for(int i=start;i<candidates.length;i++) {//继续添加数字进来
            if (!flags[i]) {
                tempList.add(candidates[i]);
                flags[i] = true;
                indexList.add(i);
            } else {
                continue;
            }

            Integer val = calc(candidates, target, flags, tempList, indexList, i);
            if (val == target) {
                List<Integer> tempAns = new ArrayList<>(tempList);
                if(!ans.contains(tempAns)){//如果与以前的没有重复，继续添加，如果出现重复，则不再添加
                    ans.add(tempAns);
                }
            }

            //本层完成后，移除上个轮次用到的数字
            tempList.remove(tempList.size() - 1);
            flags[indexList.get(indexList.size() - 1)] = false;
            indexList.remove(indexList.size() - 1);
        }
        return target+1;
    }
}

评论区效率提升了不少

class Solution {

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

    private void dfs(int[] candidates, List<Integer> path, int index, int target) {
        if(target < 0) return;

        if(target == 0) {
            res.add(new ArrayList<>(path));
            return;
        }

        for(int i = index; i < candidates.length; i++) {
            if(i > index && candidates[i] == candidates[i-1]) continue;
            path.add(candidates[i]);
            dfs(candidates, path, i+1, target-candidates[i]);
            path.remove(path.size()-1);
        }
    }
}

官方题解

class Solution {
    List<int[]> freq = new ArrayList<int[]>();
    List<List<Integer>> ans = new ArrayList<List<Integer>>();
    List<Integer> sequence = new ArrayList<Integer>();

    public List<List<Integer>> combinationSum2(int[] candidates, int target) {
        Arrays.sort(candidates);
        for (int num : candidates) {
            int size = freq.size();
            if (freq.isEmpty() || num != freq.get(size - 1)[0]) {
                freq.add(new int[]{num, 1});
            } else {
                ++freq.get(size - 1)[1];
            }
        }
        dfs(0, target);
        return ans;
    }

    public void dfs(int pos, int rest) {
        if (rest == 0) {
            ans.add(new ArrayList<Integer>(sequence));
            return;
        }
        if (pos == freq.size() || rest < freq.get(pos)[0]) {
            return;
        }

        dfs(pos + 1, rest);

        int most = Math.min(rest / freq.get(pos)[0], freq.get(pos)[1]);
        for (int i = 1; i <= most; ++i) {
            sequence.add(freq.get(pos)[0]);
            dfs(pos + 1, rest - i * freq.get(pos)[0]);
        }
        for (int i = 1; i <= most; ++i) {
            sequence.remove(sequence.size() - 1);
        }
    }
}

作者：LeetCode-Solution
链接：https://leetcode-cn.com/problems/combination-sum-ii/solution/zu-he-zong-he-ii-by-leetcode-solution/
来源：力扣（LeetCode）
著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。