77. Combinations

📝 Problem Details

• Title: 77. Combinations
• Link: https://leetcode.com/problems/combinations/
• Difficulty: Medium
• Tags/Categories: Backtracking

💡 Explanation of Solution

backtracking approach:
- start from the number 1 and try to build a combination recursively 
- at each recursive call, we can only choose numbers that haven't been chosen yet and are greater than the last added number (to maintain increasing order and avoid duplicates)
- we stop exploring a path once the current combination reaches size k
- to optimize, we calculate how many numbers are left to fill the combination (need) and how many are available (remain), pruning early when not enough numbers remain

⌛ Complexity Analysis

Time Complexity: O(C(n, k))
- We generate all possible combinations of size k from n elements.
- The number of such combinations is C(n, k) = n! / (k! * (n - k)!)

Space Complexity: O(k)
- We use a temporary list `curr` of size at most k during recursion.
- The result list `ans` takes O(C(n, k) * k) space in total, but that’s output space.

💻 Implementation of Solution

class Solution {
public:
    vector<vector<int>> combine(int n, int k) {
        vector<vector<int>> ans;
        vector<int> curr;
        backtrack(curr, 1, ans,k,n);
        return ans;
    }
    void backtrack(vector<int> curr, int firstNum, vector<vector<int>>& ans, int k, int n) {
        // early exit if we've reached a fully constructed combination
        if(curr.size() == k) {
            ans.push_back(curr);
            return;
        }
 
        int need = k - curr.size();
        int remain = n - firstNum + 1;
        int available = remain - need;
 
        for(int num = firstNum; num <= firstNum + available; num++) {
            curr.push_back(num);
            backtrack(curr,num+1, ans, k, n);
            curr.pop_back();
        }
    }
};