> 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-12-2022-216.md).

# 02/12/2022 216

**Method:**

**Backtraking: similar way with the no.77 problem.  But there is one more parameter sum in the backtracking function.  The base condition is when the path.size == k and if the targetsum = sum, add new ArrayList(path) into result, else just return.  In the for loop, noted when you do path.add(i), sum = sum + i, after recursion of backtracking function, you should corresponding path.remove and sum = sum - i.** 

**Time O(k \*c(9,k))**

**O(k \* p(9,k))**

**Space O(k)**

* Space Complexity: \mathcal{O}(K)O(K)
  * During the backtracking, we used a list to keep the current combination, which holds up to KK elements, *i.e.* \mathcal{O}(K)O(K).
  * Since we employed recursion in the backtracking, we would need some additional space for the function call stack, which could pile up to K consecutive invocations, *i.e.*O(K).
  * Hence, to sum up, the overall space complexity would be O(K).
  * **Note that**, we did not take into account the space for the final results in the space complexity.

 However, we would like to highlight a key ***trick*** that we employed, in order to ensure the ***non-redundancy*** among the digits within a single combination, as well as the ***non-redundancy*** among the combinations.

> The trick is that we pick the candidates ***in order***. We treat the candidate digits as a list with order, *i.e.* `[1, 2, 3, 4, 5, 6, 7, 8. 9]`. At any given step, once we pick a digit, *e.g.* `6`, we will not consider any digits before the chosen digit for the following steps, *e.g.* the candidates are reduced down to `[7, 8, 9]`.

so the reason you need it is because list is an object which you are always adding and removing from. If you add that object to result, that object is still the same object being referenced which you are adding and removing to. You thus need to create a new list object each time you obtain a solution.

In order words ArrayList\<ArrayList> is a list of ArrayList objects simply adding result.add(list) you would be adding the same list object over and over. And since each of those list is always the same object (they all point to the same list object) they would all look the same in the end, in this case empty since you always remove the element you add to the list.

Hopefully that makes sense. Let me know if it doesn't I can try to clear it up for you

**别忘了处理过程 和 回溯过程是一一对应的，处理有加，回溯就要有减！！！！！！！**

class Solution {

```
List<List<Integer>> result = new ArrayList<>();
LinkedList<Integer> path = new LinkedList<>();

public List<List<Integer>> combinationSum3(int k, int n) {
    backtracking(n, k, 1, 0);
    return result;    
}

private void backtracking(int targetSum, int k, int startIndex, int sum){
    //base condition
    if(path.size() == k){
        if(sum == targetSum){
            result.add(new ArrayList(path));
        return;
        }
    }
    for(int i = startIndex; i <= 9; i++){
        path.add(i);
        sum += i;
        backtracking(targetSum, k, i + 1, sum);
        path.removeLast();
        sum -= i;
    }
    
}
```

}

class Solution {

```
List<List<Integer>> result = new ArrayList<>();
LinkedList<Integer> path = new LinkedList<>();

public List<List<Integer>> combinationSum3(int k, int n) {
    backtracking(n, k, 1, 0);
    return result;    
}  
private void backtracking(int targetSum, int k, int startIndex, int sum){
    //base condition
    //optimized
    if(sum > targetSum) return;
    if(path.size() == k){
        if(sum == targetSum){
            result.add(new ArrayList(path));
        return;
        }
    }
    for(int i = startIndex; i <= 9 - (k - path.size()) + 1; i++){
        path.add(i);
        sum += i;
        backtracking(targetSum, k, i + 1, sum);
        path.removeLast();
        sum -= i;
    }
    
}
```