Problem Statement

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.

LeetCode:

• https://leetcode.com/problems/combinations/description/

Constraints

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

Examples

Example 1:

Input; n = 4, k = 2
Output: [
         [1, 2],
         [1, 3],
         [1, 4],
         [2, 3],
         [2, 4],
         [3, 4]
        ]

Explanation: There are 4 choose 2 = 6 total combinations.
Note that combinations are unordered, i.e., [1,2] and [2,1] are considered to be the same combination.

Example 2:

Input: n = 1, k = 1
Output: [
         [1]
        ]

Explanation: There is 1 choose 1 = 1 total combination.

Different Approaches

1️⃣ Backtracking

We use a recursive approach to build combinations incrementally, starting from 1 up to n.

At each step:

• You can choose the current number.
• Move to the next number (to avoid duplicates and maintain order).
• Stop when your current combination has k elements.

Code:

void backtrack(int start, int n, int k, vector<int>& temp, vector<vector<int>>& res) {
    // If the current combination is of size k, add to result
    if (temp.size() == k) {
        res.push_back(temp);
        return;
    }

    // Iterate through remaining numbers starting from 'start'
    for (int i = start; i <= n; ++i) {
        temp.push_back(i);                     // Choose i
        backtrack(i + 1, n, k, temp, res);     // Recurse with i + 1
        temp.pop_back();                       // Backtrack
    }
}

vector<vector<int>> combine(int n, int k) {
    vector<vector<int>> res;
    vector<int> temp;
    backtrack(1, n, k, temp, res);
    return res;
}

Complexity Analysis:

• Time Complexity:O(C(n, k) × k)
  • Total combinations = C(n, k) (binomial coefficient)
  • Each combination takes O(k) time to construct.
• Space Complexity:O(k) (recursion stack depth) + O(C(n, k) × k) for result