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

n=5, k=3

key is the current selected element is smaller than the next one, so start from the current position then recursive to next position.

public List<List<Integer>> combine(int n, int k) {
        List<List<Integer>> results = new ArrayList<List<Integer>>();

        combine(results, new ArrayList<Integer>(), n, k, 0);

        return results;
    }

    private void combine(List<List<Integer>> results, List<Integer> result, int n, int k, int level) {
        if (result.size()==k) {
            results.add(new ArrayList<Integer>(result));
            return;
        }

        //try each possibility number in current position
        for (int i=level; i<n; i++) {
            result.add(i+1);
            // after selecting number for current position, process next position, why here is i+1 not level+1, because we need to make sure the next element is larger than the current element, level+1 will use the already used element in previous loop again.
            combine(results, result, n, k, i+1);
            result.remove(result.size()-1);
        }
    }