2020-05-02 40. Combination Sum I

Given a collection of candidate numbers (candidates) and a target number (target), find all unique combinations in candidateswhere the candidate numbers sums to target.

Each number in candidatesmay only be used once in the combination.

Note:

All numbers (including target) will be positive integers.

The solution set must not contain duplicate combinations.

Example 1:

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]]

Example 2:

Input:candidates = [2,5,2,1,2], target = 5,A solution set is:[  [1,2,2],  [5]]

比起Combination sum，增加一个条件，同一个回溯层级里面，不遍历已经处理过的元素就好，就是这行代码：

            if (i > curIndex && candidates[i] == candidates[i - 1]) continue;

完整代码：

class Solution {

    public List<List<Integer>> combinationSum2(int[] candidates, int target) {

        Arrays.sort(candidates);

        List<List<Integer>> res = new LinkedList<>();

        List<Integer> cur = new LinkedList<>();

        backtrace(candidates, cur, res, target, 0, 0);

        return res;

    }

    private void backtrace(int[] candidates, List<Integer> cur, List<List<Integer>> res, int target, int curSum, int curIndex) {

        if (curSum == target) {

            res.add(new ArrayList<>(cur));

            return;

        } else if (curSum > target) {

            return;

        }

        for (int i = curIndex; i < candidates.length && curSum + candidates[i] <= target; i++) {

            if (i > curIndex && candidates[i] == candidates[i - 1]) continue;

            cur.add(candidates[i]);

            curSum += candidates[i];

            backtrace(candidates, cur, res, target, curSum, i + 1);

            curSum -= candidates[i];

            cur.remove(cur.size() - 1);

        }

    }

}