Given a set of unique candidate numbers and a target number, find all unique combinations of candidates, where each combination sums to target. Each candidate may be used repeatedly.
My solution is https://github.com/tiger40490/repo1/blob/cpp1/cpp/combo_permu/comboSum.cpp , showing a reusable backtracking technique described below. It’s clever and brief. However, the efficiency is questionable. Memoization might be applicable here.
This backtracking relies on a key insight. Suppose we have target = 7 and X=2,Y=3,Z=4 as the candidates.
- when we try a Y, we don’t need to try any more Xs. For example, If we are trying XY, then all XX* solutions are already handled by earlier recursive calls.
- each combo sequence is naturally pre-sorted internally.
- Also, “lower” formulas are generated before “higher” formulas
root x y z / | \ x y z / \ | \ \ xxx xxy | xyz \ xyy xzz
void //can return something if needed recurs( solutionsFound &, //growing curPartialSolution &, // above collections could be global variables, to simplify things remainingCandidates, /*probably an immutable global array. If we need the remaining array to shrink, we can still rely on startIndex to skip used candidates.*/ gapFromTarget, startIndex, //used to select from remaining candidates )
Inside this function, we scan remaining candidates starting from startIndex. Typically in one iteration
- we add a new candidate into curPartialSolution
- we call recurs
- we remove the last added candidate from curPartialSolution to restore the original curPartialSolution — backtracking up the tree.
- move on to the next candidate
I feel this is more greedy than DP