Combinations

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

Have you met this question in a real interview? 

Yes

Example

For example,
If n = 4 and k = 2, a solution is:
[[2,4],[3,4],[2,3],[1,2],[1,3],[1,4]]

public class Solution {

    /**

     * @param n: Given the range of numbers

     * @param k: Given the numbers of combinations

     * @return: All the combinations of k numbers out of 1..n

     */

    public List<List<Integer>> combine(int n, int k) {

// write your code here

        List<List<Integer>> res = new ArrayList<List<Integer>>();

        combinationSum(res, 1, n, new ArrayList<Integer>(), k);

        return res;

        

    }

    private void combinationSum(List<List<Integer>> res, int start, int n, List<Integer> sub, int k){

        if(k < 0) return;

        if(k == 0){

            res.add(new ArrayList<Integer>(sub));

            return;

        }

        

        for(int i = start; i <= n; i++){

            sub.add(i);

            combinationSum(res, i+1, n, sub, k-1);

            sub.remove(sub.size()-1);

        }

    }

}