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

Java

public class Solution {
    public List<List<Integer>> combine(int n, int k) {
        if(n < 0 || k < 0) {
            return null;
        }

        List<List<Integer>> sols = new ArrayList<List<Integer>>();
        List<Integer> sol = new ArrayList<Integer>();
        helper(n, k, 1, sol, sols);
        return sols;
    }

    private void helper(int n, int k, int start, List<Integer> sol, List<List<Integer>> sols) {
        if(k == 0) {
            sols.add(new ArrayList<Integer>(sol));
            return;
        }

        for(int i = start; i <= n - k + 1; i++) {
            sol.add(i);
            helper(n, k - 1, i + 1, sol, sols);
            sol.remove(sol.size() - 1);
        }
    }
}