> For the complete documentation index, see [llms.txt](https://timmybeeflin.gitbook.io/cracking-leetcode/llms.txt). Markdown versions of documentation pages are available by appending `.md` to page URLs; this page is available as [Markdown](https://timmybeeflin.gitbook.io/cracking-leetcode/dfs-and-bfs/dfs/tips/40.-combination-sum-ii-not-use-before-so-int-i-start-dfs-i+1-and-sort.md).

# 40. Combination Sum II (not use before so int I = start, dfs(i+1), and sort

time: O(2^n), candidate choose or not choose, n times

space: O(target)

```java
class Solution {
    public List<List<Integer>> combinationSum2(int[] candidates, int target) {
        List<List<Integer>> result = new ArrayList<>();
        Arrays.sort(candidates);
        dfs(result, candidates, target, new ArrayList<>(), 0);
        return result;
    }
    private void dfs(List<List<Integer>> result, int[] nums, int target, List<Integer> list, int start) {
        if (target < 0) {
            return;
        }
        if (target == 0) {
            result.add(new ArrayList<>(list));
            return;
        }
        for (int i = start; i < nums.length; i++) {
            if (i > start && nums[i] == nums[i-1]) {
                continue;
            }
            list.add(nums[i]);
            dfs(result, nums, target - nums[i], list, i+1);
            list.remove(list.size()-1);
        }
    }
}
```

### latest one

```java
class Solution {
    public List<List<Integer>> combinationSum2(int[] candidates, int target) {
        Arrays.sort(candidates);
        List<List<Integer>> result = new ArrayList<>();
        dfs(0, candidates, target, result, new ArrayList<>());
        return result;
    }
    private void dfs(int start, int[] candidates, int target, List<List<Integer>> result, List<Integer> list) {
        if (target < 0) {
            return;
        }
        if (target == 0) {
            result.add(new ArrayList<>(list));
            return;
        }
        for (int i = start; i < candidates.length; i++) {
            if (i > start && candidates[i] == candidates[i-1]) {
                continue;
            }
            // System.out.println("i="+i);
            list.add(candidates[i]);
            dfs(i+1, candidates, target - candidates[i], result, list);
            list.remove(list.size()-1);
        }
    }
}

/**
sort and compare to previous the same elments, can avoid use the same number in an array 
        Arrays.sort(candidates);
        
        // compare to previous the same elments
        if (i > start && candidates[i] == candidates[i-1]) {

        thats why we need to sort first

        ex:
         a b c d e
        [1,1,1,1,1]
        target: 2

        [1]    




        2
        /
        1a--------------  first i is start, this will add to list(list.add(candidates[i]);), then dfs() , another condition keep running next for loop -> will check duplicated (i > start, && candidates[i] == candidates[i-1]) {
        / 
        1 [1,1,1,1] -> dfs part
        / use 1b
        0 -> get ans


so first time use 1a, then others in for loop because they are all the same (i > start, && candidates[i] == candidates[i-1]
so all skip

in next dfs, use 1b, then others in for loop all skip

-> result is [1,1]

sort and compare the same number continuousely
in this way to avoid duplicated combinations

T: O(2^n), choose or not chooes
S: O(n), worst case is to use all element, so dfs call stack deep is all elements -> is n


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

sort: 1,2,2,2,5
only will use the "first" one in each dfs call
ex: 2,2,2 -> use 2a and 2b
[1,2,2]

 */
```


---

# Agent Instructions
This documentation is published with GitBook. GitBook is the documentation platform designed so that both humans and AI agents can read, navigate, and reason over technical content effectively. Learn more at gitbook.com.

## Querying This Documentation
If you need additional information that is not directly available in this page, you can query the documentation dynamically by asking a question.

Perform an HTTP GET request on the current page URL with the `ask` query parameter:

```
GET https://timmybeeflin.gitbook.io/cracking-leetcode/dfs-and-bfs/dfs/tips/40.-combination-sum-ii-not-use-before-so-int-i-start-dfs-i+1-and-sort.md?ask=<question>
```

The question should be specific, self-contained, and written in natural language.
The response will contain a direct answer to the question and relevant excerpts and sources from the documentation.

Use this mechanism when the answer is not explicitly present in the current page, you need clarification or additional context, or you want to retrieve related documentation sections.