参考别人的code, 看似不难的题，其实挺费事的。思想还是：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: [[]]
Leetcode: Combinations,布布扣,bubuko.com
原文：http://www.cnblogs.com/EdwardLiu/p/3740446.html