> 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-39.md).

# 02/14/2022 39

Method:

use backtracking. This problem is similar to question 216 except one difference: the same number may be chosen an unlimited number of times. Therefore, we still can use 216 template but need to change a little bit: in the backtracking function, when we call backtracking again, we need to put startIndex instead of startIndex + 1. We also can optimized by checking if sum + candidates\[i] > sum, if it is, we just break from the for loop.

Time (O(N^((T/M) + 1)) The maximun depth of the tree would be T/M. N is the number of candidates. T is the target value, M is the minimal candidates. At each node, it takes a constant time to process, except the leaf nodes which could take a linear time to make a copy of combination. It is the upper bound.

Space(O(T/M))

constraints:

1 <= candidates\[i] <= 200

**本题还需要startIndex来控制for循环的起始位置，对于组合问题，什么时候需要startIndex呢？**

我举过例子，如果是一个集合来求组合的话，就需要startIndex.

**注意本题和**[**77.组合**](https://programmercarl.com/0077.%E7%BB%84%E5%90%88.html)**、**[**216.组合总和III**](https://programmercarl.com/0216.%E7%BB%84%E5%90%88%E6%80%BB%E5%92%8CIII.html)**的一个区别是：本题元素为可重复选取的**。因此，startindex不需要加1.

![](/files/CQJmMcegjB6X118sAMYv)

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

```
public List<List<Integer>> combinationSum(int[] candidates, int target) {
    if(candidates == null || candidates.length == 0 || target == 0) return result;
    Arrays.sort(candidates);// for optimization.
    backtracking(candidates, target, 0, 0);
    return result;            
}

private void backtracking(int[] candidates, int target, int sum, int startIndex){
    if(sum == target){
        result.add(new ArrayList(path));
        return;
    }
    
    for(int i = startIndex; i < candidates.length; i++){
        if(sum + candidates[i]> target) return; //for optimization
        path.add(candidates[i]);
        sum += candidates[i];
        backtracking(candidates, target, sum, i);
        sum -= candidates[i];
        path.removeLast();
    }
}
```

}