1+ package Algorithms .combination ;
2+
3+ import java .util .ArrayList ;
4+ import java .util .Arrays ;
5+ import java .util .List ;
6+
7+ public class CombinationSum_1203 {
8+ public List <List <Integer >>combinationSum (int []candidates ,int target ) {
9+ List <List <Integer >>ret =new ArrayList <List <Integer >>();
10+ if (candidates ==null ||candidates .length ==0 ) {
11+ return ret ;
12+ }
13+
14+ // Sort to avoid duplicate solutions.
15+ Arrays .sort (candidates );
16+
17+ dfs (candidates ,target ,new ArrayList <Integer >(),ret ,0 );
18+ return ret ;
19+ }
20+
21+ public void dfs (int []candidates ,int target ,List <Integer >path ,List <List <Integer >>ret ,int index ) {
22+ if (target <0 ) {
23+ return ;
24+ }
25+
26+ if (target ==0 ) {
27+ ret .add (new ArrayList (path ));
28+ return ;
29+ }
30+
31+ // i 的起始值是跟排列的最主要区别。因为与顺序无关，所以我们必须只能是升序，也就是说下一个取值只能是i本身
32+ // 或是i的下一个。
33+ // 但是排列的话，可以再取前同的。1, 2 与2 1是不同的排列，但是同一个组合
34+ for (int i =index ;i <candidates .length ;i ++) {
35+ int num =candidates [i ];
36+ path .add (num );
37+
38+ // 注意，最后的参数是i，不是index!!
39+ dfs (candidates ,target -num ,path ,ret ,i );
40+ path .remove (path .size () -1 );
41+ }
42+ }
43+ }