Combination Sum

MediumBacktracking

Given distinct candidates and a target, return all unique combinations where chosen numbers sum to target. Each number may be reused unlimited times.

Open problem

Constraints

1 <= candidates.length <= 30
2 <= candidates[i] <= 40

Backtracking with start index

Time O(2^t) bounded by target/min-candidate depthSpace O(target/min) recursion depth

Try each candidate from a start index, subtracting it from the remaining target and allowing reuse by recursing at the same index. Move the start index forward to avoid duplicate combinations.

#include <bits/stdc++.h>
using namespace std;

vector<vector<int>> combinationSum(vector<int>& cand, int target) {
    vector<vector<int>> res;
    vector<int> cur;
    function<void(int,int)> bt = [&](int start, int rem) {
        if (rem == 0) { res.push_back(cur); return; }
        for (int i = start; i < (int)cand.size(); i++) {
            if (cand[i] > rem) continue;
            cur.push_back(cand[i]);
            bt(i, rem - cand[i]);
            cur.pop_back();
        }
    };
    bt(0, target);
    return res;
}