Combination

Given two integers n and k, return all possible combinations of k numbers out of 1 ... n.

• Time: O(n)
• Space: O(1)

public List<List<Integer>> combine(int n, int k) {
    List<List<Integer>> ret = new ArrayList<>();
    List<Integer> path = new ArrayList<>();
    helper(ret, path, n, 1, k);
    return ret;
}

private void helper(List<List<Integer>> ret, List<Integer> path, 
            int n, int start, int size) {
    if (size == path.size()) {
        ret.add(new ArrayList<>(path));
        return;
    }
    for (int i = start; i <= n; i++) {
        path.add(i);
        helper(ret, path, n, i + 1, size);
        path.remove(path.size() - 1);
    }
}