首页 > 代码库 > Leetcode: Combinations

Leetcode: Combinations

参考别人的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: [[]]