clueless coding // TODO: be smarter

LeetCode 40. Combination Sum II: C++ Solution



Problem Statement


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

Each number in C may only be used once in the combination.

All numbers (including target) will be positive integers.

The solution set must not contain duplicate combinations.

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

Inputs:
  candidates = [10, 1, 2, 7, 6, 1, 5]
  target = 8

Outputs:
[
  [1, 7],
  [1, 2, 5],
  [2, 6],
  [1, 1, 6]
]



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 (i != start && candidates[i] == candidates[i-1]) {
            continue;
        }

        if (target - candidates[i] >= 0) {
            current.push_back(candidates[i]);
            helper(result, candidates, current, i + 1, target - candidates[i]);
            current.pop_back();
        }
    }
}

vector<vector<int>> combinationSum2(vector<int>& candidates, int target) {
    sort(candidates.begin(), candidates.end());
    vector<vector<int>> result;
    vector<int> current;
    helper(result, candidates, current, 0, target);
    return result;
}