LeetCode 40. Combination Sum II

Problem

LeetCode 40. Combination Sum II

1. 题目简述

给出一个正整数数组A（可能存在重复），给出一个target，找出和为target的所有不重复的可能组合（每个数字最多只能使用一次）。例如：

Input: candidates = [10,1,2,7,6,1,5], target = 8,
A solution set is:
[
[1, 7],
[1, 2, 5],
[2, 6],
[1, 1, 6]
]

2. 算法思路

这道题是combination sum系列的第二题，区别在于这次不是无限适应数字了，而是每个数字都最多使用一次。其实算法类似，这道题还是不能用DP，因为每个数字只能用一次，子问题相互干涉，使用不是DP问题（下周做DP的背包问题吧，要不然太烦了，感觉跟这个combination sum好像啊）。

回溯

此题我们仍然考虑用回溯法，其实可以用combination sum I的代码，只需要在递归调用backtracking的时候将startIndex从i变为i+1而已，最后还需要将整个结果集去重（因为存在存在重复数字，假设说我们有三个1，有一种解法需要两个1和其他数字，如果不去重，这一种解法就会膨胀成三个）。

当然，还有一种更巧妙的去重方法，如果临时想的话不一定想得到，直接记忆吧，放在解法2里。

3. 解法

1. 回溯，使用hashset去重法，巨慢

class Solution {

    List<List<Integer>> res;
    Set<List<Integer>> hashset;

    public List<List<Integer>> combinationSum2(int[] candidates, int target) {
        Arrays.sort(candidates);
        hashset = new HashSet();
        LinkedList<Integer> nums = new LinkedList();

        backtracking(candidates, target, 0, 0, nums);

        res = new ArrayList(hashset);
        return res;
    }

    private void backtracking(int[] candidates, int target, int sum, int startIndex, LinkedList<Integer> nums) {
        for (int i = startIndex; i < candidates.length; i++) {
            sum += candidates[i];
            nums.add(candidates[i]);

            if (sum < target) {
                backtracking(candidates, target, sum, i + 1, nums);
                nums.removeLast();
                sum -= candidates[i];
                continue;
            } else if (sum == target) {
                hashset.add(new ArrayList(nums));
            }

            nums.removeLast();
            return;
        }
    }
}

2. 回溯，循环判断去重，优雅。

class Solution {

    List<List<Integer>> res;

    public List<List<Integer>> combinationSum2(int[] candidates, int target) {
        Arrays.sort(candidates);
        LinkedList<Integer> nums = new LinkedList();
         res = new ArrayList();

        backtracking(candidates, target, 0, 0, nums);

        return res;
    }

    private void backtracking(int[] candidates, int target, int sum, int startIndex, LinkedList<Integer> nums) {
        for (int i = startIndex; i < candidates.length; i++) {

            // 优雅的去重方式，记住，以后可能用得到！
            if (i > startIndex && candidates[i - 1] == candidates[i]) {
                continue;
            }

            sum += candidates[i];
            nums.add(candidates[i]);

            if (sum < target) {
                backtracking(candidates, target, sum, i + 1, nums);
                nums.removeLast();
                sum -= candidates[i];
                continue;
            } else if (sum == target) {
                res.add(new ArrayList(nums));
            }

            nums.removeLast();
            return;
        }
    }
}