LC.77.Combinations

https://leetcode.com/problems/combinations/description/

Given two integers n and k, return all possible combinations of k numbers out of 1 ... n.

For example,
If n = 4 and k = 2, a solution is:

[
  [2,4],
  [3,4],
  [2,3],
  [1,2],
  [1,3],
  [1,4],
]

 1 public List<List<Integer>> combine(int n, int k) {
 2         List<List<Integer>> res = new ArrayList<>();
 3         if (n == 0 || k<0) {
 4             return res ;
 5         }
 6         dfs(n,k,0,new ArrayList<>(), res);
 7         return res ;
 8     }
 9 
10     private void dfs(int n, int k, int index , ArrayList<> subRes, List<List<Integer>> res ) {
11         //terminate :
12         if (index == k) {
13             //deep copy
14             res.add(new ArrayList<>(subRes)) ;
15             return res ;
16         }
17         for (int i = index; i <= n ; i++ ) {
18             //add
19             subRes.add(i) ;
20             //不能有重复
21             dfs(n, k, i+1, subRes, res);
22             //remove
23             subRes.remove(subRes.size()-1) ;
24         }
25     }