# LeetCode 40. Combination Sum II

## Description

https://leetcode.com/problems/combination-sum-ii/description/

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

Each number in C 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.

For example, given candidate set `[10, 1, 2, 7, 6, 1, 5]` and target `8`,
A solution set is:

```[
[1, 7],
[1, 2, 5],
[2, 6],
[1, 1, 6]
]```

## Explanation

Combinations are subsets of the candidate array. We can use depth-first search to find all combinations of the input array. First, sort candidates array into ascending order.
Second, conduct a depth-first search to visit each combination of the input array.

A depth-first search function would be:
Whenever adding an element to the combination, we reduce the target.
If the remaining target value is equal to 0, we add the current combination to the result list.
Then, recursively find all combinations for the remaining target value from the remaining elements.

## Java Solution

```class Solution {
public List<List<Integer>> combinationSum2(int[] candidates, int target) {
List<List<Integer>> results = new ArrayList<>();

if (candidates == null || candidates.length == 0) {
return results;
}

Arrays.sort(candidates);

List<Integer> combination = new ArrayList<>();
toFindCombinationsToTarget(candidates, results, combination, 0, target);

return results;
}

private void toFindCombinationsToTarget(int[] candidates, List<List<Integer>> results, List<Integer> combination, int startIndex, int target) {
if (target == 0) {
return;
}

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

if (candidates[i] > target) {
break;
}