leetcode 40. 组合总和 II

记录受上一题影响以及没有融会贯通导致失败的leetcode 40. 组合总和 II

题目

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

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

注意：解集不能包含重复的组合。

示例 1:

输入: candidates = [10,1,2,7,6,1,5], target = 8,
输出:
[
[1,1,6],
[1,2,5],
[1,7],
[2,6]
]
示例 2:

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

提示:

1 <= candidates.length <= 100
1 <= candidates[i] <= 50
1 <= target <= 30

思路

乍一想应该和leetcode 39类似的，只不过这里要求元素不能被重复用了，那就每次dfs的时候循环开始的idx+1就好了。于是直接WA了，发现要求结果中不能重复。例如示例1会出现[7, 1], [7, 1]，因为有两个1，都能用。我这一想那就每次加的时候判断重复没把，于是有了第一版代码（我甚至让list里的subList只排序一次了，谢），但TLE。看了解析，原来是要在加入元素到subList时候就要判断是否重复了，如果当前元素和上一个重了那肯定就有判断过了因此去掉，因此写了第二版，麻了仔细想想和三数之和还有四数之和还有异曲同工之妙，要好好融会贯通一下。

代码

// 第一版
class Solution {
    public List<List<Integer>> list = new ArrayList<>();
    public List<Integer> subList = new ArrayList<>();

    public List<List<Integer>> combinationSum2(int[] candidates, int target) {
        Arrays.sort(candidates);
        desc(candidates);
        dfs(candidates, target, 0, 0);
        return list;
    }

    public void desc(int[] candidates) {
        int i = 0, j = candidates.length - 1;
        while(i < j) {
            int tmp = candidates[i];
            candidates[i] = candidates[j];
            candidates[j] = tmp;
            i++;
            j--;
        }
    }

    public boolean equal(List<Integer> a, List<Integer> b) {
        for (int i=0;i<a.size();i++) {
            if (a.get(i) != b.get(i)) {return false;}
        }
        return true;
    }

    public boolean exist(List<Integer> l) {
        Collections.sort(l);
        for(List<Integer> item : list) {
            if (item.size() != l.size()) {continue;}
            // item都是l加进来的，不用排序了
            // Collections.sort(item);
            if (equal(item, l)) {return true;}
        }
        return false;
    }

    public void dfs(int[] candidates, int target, int cnt, int idx) {
        if (cnt > target) {return;}
        else if (cnt == target) {
            List<Integer> l = new ArrayList<>(subList);
            if (exist(l)) {return;}
            list.add(new ArrayList<>(subList));
            return;
        }
        for (int i=idx;i<candidates.length;i++) {
            subList.add(candidates[i]);
            cnt += candidates[i];
            dfs(candidates, target, cnt, i + 1);
            subList.remove(subList.size() - 1);
            cnt -= candidates[i];
        }
    }
}
// 第二版
class Solution {
    public List<List<Integer>> list = new ArrayList<>();
    public List<Integer> subList = new ArrayList<>();

    public List<List<Integer>> combinationSum2(int[] candidates, int target) {
        Arrays.sort(candidates);
        desc(candidates);
        dfs(candidates, target, 0, 0);
        return list;
    }

    public void desc(int[] candidates) {
        int i = 0, j = candidates.length - 1;
        while(i < j) {
            int tmp = candidates[i];
            candidates[i] = candidates[j];
            candidates[j] = tmp;
            i++;
            j--;
        }
    }

    public void dfs(int[] candidates, int target, int cnt, int idx) {
        if (cnt > target) {return;}
        else if (cnt == target) {
            list.add(new ArrayList<>(subList));
            return;
        }
        for (int i=idx;i<candidates.length;i++) {
            if (i > idx && candidates[i] == candidates[i-1]) {continue;}
            subList.add(candidates[i]);
            cnt += candidates[i];
            dfs(candidates, target, cnt, i + 1);
            subList.remove(subList.size() - 1);
            cnt -= candidates[i];
        }
    }
}