Q: https://leetcode.com/problems/combination-sum/description/

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