> For the complete documentation index, see [llms.txt](https://emmaguo100.gitbook.io/leetcode/llms.txt). Markdown versions of documentation pages are available by appending `.md` to page URLs; this page is available as [Markdown](https://emmaguo100.gitbook.io/leetcode/02-14-2022-40.md).

# 02/14/2022 40

40\. Combination Sum II

Method:

This question has two differences from the 39th question. 

1, there are duplicate candidates

2, each element can only be used once.

So the main difficulty is to avoid duplicates in the combinations.  So in the for loop, we have to check if i > startIndex and if arr\[i] == arr\[i-1]. If it is, just continue.

Time O(2^n)

Space O(n)

class Solution { List\<List> lists = new ArrayList<>(); LinkedList path = new LinkedList<>();

```
public List<List<Integer>> combinationSum2(int[] candidates, int target) {
    Arrays.sort(candidates);
    backTracking(candidates, target, 0, 0);
    return lists;
}
public void backTracking(int[] arr, int target, int sum, int startIndex) {
    if (sum == target) {
        lists.add(new ArrayList(path));
        return;
    }
    //OPTIMIZED 
    for (int i = startIndex; i < arr.length && arr[i] + sum <= target; i++) {
        //to avoid duplicates
        if(i > startIndex && arr[i] == arr[i-1]) continue;
        sum += arr[i];
        path.add(arr[i]);
        backTracking(arr, target, sum, i + 1);
        sum -= arr[i];
        path.removeLast();
    }
}
```

}