BiruLyu
5/30/2017 - 2:18 AM

77. Combinations.java

public class Solution {
    public List<List<Integer>> combine(int n, int k) {
        List<List<Integer>> res = new ArrayList<List<Integer>>();
        List<Integer> temp = new ArrayList<Integer>();
        backtracking(n, k, 1, temp, res);
        return res;
    }
    
    public void backtracking(int n, int k, int start, List<Integer> temp, List<List<Integer>> res) {
        
        if( k == 0) {
            res.add(new ArrayList(temp));
            return;
        }
        
        for(int i = start; i <= n - k + 1; i++) { // n - k + 1!!!!!!
            temp.add(i);
            backtracking(n, k - 1, i + 1, temp, res);
            temp.remove(temp.size()-1);
        }
        
    }
}