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

Solution:
All combination questions in leetcode can be solved using dfs. 

public class Solution {
    public ArrayList<ArrayList<Integer>> combine(int n, int k) {
        ArrayList<ArrayList<Integer>> results = new ArrayList<ArrayList<Integer>>();
        ArrayList<Integer> subset = new ArrayList<Integer>();
        if(k == 0 || n == 0) return results;
        helper(n, k, 1, results, subset);
        return results;
    }
    public void helper(int n, int k, int begin, ArrayList<ArrayList<Integer>> results, ArrayList<Integer> subset){
        if(subset.size() == k){
            ArrayList<Integer> temp = new ArrayList<Integer>(subset); 
            results.add(temp);
            return;
        }
        for(int i = begin; i <= n; i++){
            subset.add(i);
            helper(n,k,i+1,results,subset);
            subset.remove(subset.size()-1); // remove the last element
        }
    }
}