首页 > itarticle > [leetcode] problem 40 – combination sum ii

[leetcode] problem 40 – combination sum ii

admin 11月 13, 2020 0

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

Each number in candidates may 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

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

No.2

Input: candidates = [2,5,2,1,2], target = 5,

A solution set is:
[
  [1,2,2],
  [5]
]

Code

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

    combinationSum2Helper(result, combination, candidates, target, 0);

    return result;
}

private void (List<List<Integer>> result, List<Integer> combination, int[] candidates, int target, int idx) {
    if (target < 0)
        return;

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

    for (int i = idx; i < candidates.length; i++) {
        if (i > idx && candidates[i] == candidates[i - 1])
            continue;

        combination.add(candidates[i]);
        combinationSum2Helper(result, combination, candidates, target - candidates[i], i + 1);
        combination.remove(combination.size() - 1);
    }
}