Leetcode: Combinations

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],
]

参考别人的code, 看似不难的题，其实有点小难的，recursive function并不好写。思想还是：From this example, we can see that in the first position of the resulting combinations we can chose number 1-5. Assume that we chose 1 for the 1 position of the combination, then we can choose 2-5 for the second position. Till we chosen numbers for all position, we can have one possible combination.

However, when we chose 3 for the first position and 5 for the second position, we don't have any other number to choose for the 3rd position. (former number must be smaller than the following number).

 1 public class Solution {
 2     public ArrayList<ArrayList<Integer>> combine(int n, int k) {
 3         ArrayList<Integer> set = new ArrayList<Integer>();
 4         ArrayList<ArrayList<Integer>> sets= new ArrayList<ArrayList<Integer>>();
 5         
 6         if (n < k) return sets;
 7         helper(set, sets, 1, n, k);
 8         return sets;
 9     }
10     
11     public void helper(ArrayList<Integer> set, ArrayList<ArrayList<Integer>> sets, int starter, int n, int k) {
12         if (set.size() == k) {
13             sets.add(new ArrayList<Integer>(set));
14             return;
15         }
16         
17         else {
18             
19             for (int j = starter; j <= n; j++) {
20                 set.add(j);
21                 helper(set, sets, j+1, n, k);
22                 set.remove(set.size()-1);
23             }
24         }
25     }
26 }

sets.add(new ArrayList<Integer>(set)); 要特别注意，我写成sets.add(set)就会在以下情况报错：input为： 1,1; expected：[[1]], output: [[]]