77. Combinations

Description

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

You may return the answer in any order.

Constraints

1 <= k <= n

Approach

Backtracking

Examples

Input: n = 4, k = 2

Output: [ [1, 2], [1, 3], [1, 4], [2, 3], [2, 4], [3, 4] ]

Solutions

/**
 * Time complexity : O(k*kCn), where kCn = n!/((n-k)! * k!) is a number of 
 *    combinations to build. append / pop (add / removeLast) operations are 
 *    constant-time ones and the only consuming part here is to append the 
 *    built combination of length k to the output.
 * Space complexity : O(kCn) to keep all the combinations for an output.
 */

class Solution {
    public List<List<Integer>> combine(int n, int k) {
        List<List<Integer>> resultList = new ArrayList<>();
        backtrack(resultList, new ArrayList(), 1, n, k);
        return resultList;
    }
    private void backtrack(List<List<Integer>> resultList, 
                              List<Integer> currList,
                              int start,
                              int end,
                              int k ) {
        if(k == 0) {
            resultList.add(new ArrayList(currList));
            return;
        }
        for(int i = start; i <= end-k+1; i++) {
            currList.add(i);
            backtrack(resultList, currList, i+1, end, k-1);
            currList.remove(currList.size()-1);
        }
    }
}