leetcode8/Combinations.java at master · 1code/leetcode8 · GitHub

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
//backTracking solution, O(N!/K!)
public class Solution {
    public ArrayList<ArrayList<Integer>> combine(int n, int k) {
        // Start typing your Java solution below
        // DO NOT write main() function
        ArrayList<ArrayList<Integer>> results = new ArrayList<ArrayList<Integer>>();
        ArrayList<Integer> result = new ArrayList<Integer>();
        combine(n, k, 1, result, results);
        return results;
    }

    public void combine(int n, int k, int index,
    ArrayList<Integer> result, ArrayList<ArrayList<Integer>> results){
        for(int i = index; i <= n; ++i){
            result.add(i);
            if(k > 1)
                combine(n, k - 1, i + 1, result, results);
            else
                results.add(new ArrayList<Integer>(result));
            result.remove(result.size() - 1);
        }
    }
}

//recursion, O(N!/K!)
public class Solution {
    public ArrayList<ArrayList<Integer>> combine(int n, int k) {
        // Start typing your Java solution below
        // DO NOT write main() function
        ArrayList<ArrayList<Integer>> results = new ArrayList<ArrayList<Integer>>();
        if(k == 1){
            for(int i = n; i > 0; --i){
                ArrayList<Integer> result = new ArrayList<Integer>();
                result.add(i);
                results.add(result);
            }
        }
        else{
            for(int i = n; i > 0; --i){
                for(ArrayList<Integer> result: combine(i - 1, k - 1)){
                    result.add(i);
                    results.add(result);
                }
            }
        }
        return results;
    }
}