> For the complete documentation index, see [llms.txt](https://ucan.gitbook.io/notes/llms.txt). Markdown versions of documentation pages are available by appending `.md` to page URLs; this page is available as [Markdown](https://ucan.gitbook.io/notes/backtrack/40.-combination-sum-ii.md).

# 40. Combination Sum II

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

Each number in `candidates` may only be used **once** in the combination.

**Note:** The solution set must not contain duplicate combinations.

```java
class Solution {
    public List<List<Integer>> combinationSum2(int[] candidates, int target) {
        List<List<Integer>> res =  new ArrayList<>();
        Arrays.sort(candidates);
        dfs(candidates, target, res, new ArrayList<>(), 0);
        return res;   
    }
    
    private void dfs(int[] candidates, int target, List<List<Integer>> res, List<Integer> ans, int start){
        if (target == 0){
            res.add(new ArrayList<>(ans));
        }
        if (target<=0) return;
        
        for (int i=start; i<candidates.length; i++){
            // i>start to make sure duplicated number is allowed in different depth
            // candidates[i]==candidates[i-1] avoid duplication in same depth
            if (i>start && candidates[i]==candidates[i-1]) continue;
            ans.add(candidates[i]);
            dfs(candidates, target-candidates[i], res, ans, i+1);
            ans.remove(ans.size()-1);
        }
    }
}
```