clueless coding // TODO: be smarter

LeetCode 216. Combination Sum III: C++ Solution



Problem Statement


Find all possible combinations of k numbers that add up to a number n, given that only numbers from 1 to 9 can be used and each combination should be a unique set of numbers.

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

Inputs:
  k = 3
  n = 7

Outputs:
[
  [1,2,4]
]

Inputs:
  k = 3
  n = 9

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



TL;DR Code Solution


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

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

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