clueless coding // TODO: be smarter

LeetCode 39. Combination Sum: C++ Solution



Problem Statement


Given a set of candidate integers (without duplicates) and a target number (T), find all unique combinations in C where the candidate numbers sums to T.

The same repeated number may be chosen from C unlimited number of times.

All numbers (including target) will be positive integers.

The solution set must not contain duplicate combinations.

Function Signature (C++):
  vector<vector<int>> combinationSum(vector<int>& candidates, int target)

Inputs:
  candidates = [2, 3, 6, 7]
  target = 7

Outputs:
[
  [7],
  [2, 2, 3]
]



TL;DR Code Solution


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

    for (int i = start; i < candidates.size(); i++) {
        if (target - candidates[i] >= 0) {
            current.push_back(candidates[i]);
            helper(result, candidates, current, i, target - candidates[i]);
            current.pop_back();
        }
    }
}

vector<vector<int>> combinationSum(vector<int>& candidates, int target) {
    vector<vector<int>> result;
    vector<int> current;
    helper(result, candidates, current, 0, target);
    return result;
}