clueless coding // TODO: be smarter

LeetCode 77. Combinations: C++ Solution



Problem Statement


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

Function Signature (C++):
  vector<vector<int>> combine(int n, int k)

Inputs:
  n = 4
  k = 2

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



TL;DR Code Solution


void helper(vector<vector<int>>& result, vector<int> current, int start, int n, int k) {
    if (current.size() == k) {
        result.push_back(current);
        return;
    }

    for (int i = start; i <= n; i++) {
        current.push_back(i);
        helper(result, current, i + 1, n, k);
        current.pop_back();
    }
}    

vector<vector<int>> combine(int n, int k) {
    vector<vector<int>> result;
    vector<int> current;
    helper(result, current, 1, n, k);
    return result;
}