Description

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

DFS

class Solution {
    public List<List<Integer>> combine(int n, int k) {
        List<List<Integer>> combinations = new ArrayList<>();
        if (n < 1 || k < 1 || k > n) return combinations;
        
        List<Integer> combination = new ArrayList<>();
        combineRecur(1, n, k, combination, combinations);
        return combinations;
    }
    
    public void combineRecur(int begin, int end, int count
                             , List<Integer> combination
                             , List<List<Integer>> combinations) {
        if (count == 0) {
            combinations.add(new ArrayList<>(combination));
            return;
        }

        for (int i = begin; i <= Math.min(end, end + 1 - count); ++i) {
            combination.add(i);
            combineRecur(i + 1, end, count - 1, combination, combinations);
            combination.remove(combination.size() - 1);
        }
    }
}