Medium

Combinations

Given two integers `n` and `k`, return all possible combinations of `k` numbers chosen from the range `[1, n]`. You may return the answer in any order.

Examples

Input:n = 4, k = 2

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

There are 6 possible combinations of size 2 from the range [1, 4].

Input:n = 1, k = 1

Output:[[1]]

There is only 1 combination of size 1 from the range [1, 1].

Constraints

1 <= n <= 20
1 <= k <= n

Backtracking

Approach

We can use backtracking to generate all combinations of size `k`. We iterate through the numbers from `start` to `n`. For each number, we add it to our current combination and recursively call the backtrack function with `start + 1`. Once our combination reaches size `k`, we add a copy of it to the result and backtrack by removing the last element.

Complexity Analysis

Time Complexity

O(k * C(n, k))

Space Complexity

O(k)

The time complexity corresponds to the number of combinations, C(n, k), multiplied by k to copy each combination. Space complexity is O(k) for the recursion stack and the current list.

Solution.java

1class Solution {2    public List<List<Integer>> combine(int n, int k) {3        List<List<Integer>> result = new ArrayList<>();4        backtrack(1, n, k, new ArrayList<>(), result);5        return result;6    }7    8    private void backtrack(int start, int n, int k, List<Integer> current, List<List<Integer>> result) {9        // Base case: combination is of size k10        if (current.size() == k) {11            result.add(new ArrayList<>(current));12            return;13        }14        15        // Iterate through possible candidates16        // We can optimize the upper bound: n - (k - current.size()) + 117        for (int i = start; i <= n; i++) {18            current.add(i);19            backtrack(i + 1, n, k, current, result);20            current.remove(current.size() - 1); // backtrack21        }22    }23}