Problem Statement (LeetCode 77)

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.

Example 1

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

Example 2

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

Basic Backtracking Solution

Approach

Use recursive backtracking to build combinations incrementally:

1. Maintain a current combination path and a global list of all valid combinations.
2. When the length of the current path equals k, add it to the result list and return.
3. Iterate over possible next elements starting from the given start index, add each element to the current path, recurse with the next start index, then remove the element (backtrack) to try other options.

Code

#include <iostream>
#include <vector>
using namespace std;

class Solution {
public:
    vector<vector<int>> all_combinations;
    vector<int> current_comb;

    void backtrack(int n, int k, int start_idx) {
        if (current_comb.size() == k) {
            all_combinations.push_back(current_comb);
            return;
        }

        for (int i = start_idx; i <= n; ++i) {
            current_comb.push_back(i);
            backtrack(n, k, i + 1);
            current_comb.pop_back();
        }
    }

    vector<vector<int>> combine(int n, int k) {
        all_combinations.clear();
        current_comb.clear();
        backtrack(n, k, 1);
        return all_combinations;
    }
};

Pruned Backtracking Optimization

Approach

Optimize the basic solution by reducing unnecessary iterations: The maximum starting index for the next element can be calculated as n - (k - current_comb.size()) + 1. This avoids looping over indices where there aren't enough remaining numbers to fill the required combination length.

Code

#include <iostream>
#include <vector>
using namespace std;

class OptimizedSolution {
public:
    vector<vector<int>> all_combinations;
    vector<int> current_comb;

    void backtrack(int n, int k, int start_idx) {
        if (current_comb.size() == k) {
            all_combinations.push_back(current_comb);
            return;
        }

        for (int i = start_idx; i <= n - (k - current_comb.size()) + 1; ++i) {
            current_comb.push_back(i);
            backtrack(n, k, i + 1);
            current_comb.pop_back();
        }
    }

    vector<vector<int>> combine(int n, int k) {
        all_combinations.clear();
        current_comb.clear();
        backtrack(n, k, 1);
        return all_combinations;
    }
};

Test Driver Code

int main() {
    OptimizedSolution sol;
    vector<vector<int>> results;
    int n, k;

    cout << "Enter n: ";
    cin >> n;
    cout << "Enter k: ";
    cin >> k;

    results = sol.combine(n, k);

    cout << "All valid combinations:" << endl;
    for (const auto& comb : results) {
        for (int num : comb) {
            cout << num << "  ";
        }
        cout << endl;
    }
    return 0;
}