1+ package Algorithms .combination ;
2+ import java .util .ArrayList ;
3+ import java .util .List ;
4+
5+ public class Combine_1203 {
6+ public List <List <Integer >>combine (int n ,int k ) {
7+ List <List <Integer >>ret =new ArrayList <List <Integer >>();
8+ if (k ==0 ) {
9+ ret .add (new ArrayList <Integer >());
10+ return ret ;
11+ }
12+
13+ // 注意:start应该从1开始。因为我们的数字是1
14+ dfs (n ,k ,new ArrayList <Integer >(),ret ,1 );
15+ return ret ;
16+ }
17+
18+ // SOLUTION 1:
19+ // 注意，因为求的是组合，所以我们要考虑一下顺序问题，只需要考虑升序。这样的话就不会有重复的
20+ // 的组合。
21+ public void dfs1 (int n ,int k ,List <Integer >path ,List <List <Integer >>ret ,int start ) {
22+ if (path .size () ==k ) {
23+ ret .add (new ArrayList <Integer >(path ));
24+ return ;
25+ }
26+
27+ // 注意这里的条件i <= n 取n也是合法的！
28+ // Example:
29+ for (int i =start ;i <=n ;i ++) {
30+ path .add (i );
31+
32+ // 注意，最后一个参数是i + 1，不是start + 1！！
33+ dfs (n ,k ,path ,ret ,i +1 );
34+ path .remove (path .size () -1 );
35+ }
36+ }
37+
38+ // SOLUTION 2:
39+ public void dfs (int n ,int k ,List <Integer >path ,List <List <Integer >>ret ,int start ) {
40+ if (0 ==k ) {
41+ ret .add (new ArrayList <Integer >(path ));
42+ return ;
43+ }
44+
45+ // 注意这里的条件i <= n 取n也是合法的！
46+ // Example:
47+ for (int i =start ;i <= (n -k +1 );i ++) {
48+ path .add (i );
49+
50+ // 注意，最后一个参数是i + 1，不是start + 1！！
51+ dfs (n ,k -1 ,path ,ret ,i +1 );
52+ path .remove (path .size () -1 );
53+ }
54+ }
55+ }