Combination Sum — Interview Guide

• Sort candidates first so you can prune when the running sum exceeds the target.
• Recurse with the same index (unlimited use) but never go back to an earlier index (avoids permutations of the same combo).
• Copy the current combination before adding it to the result.

def combination_sum(cands, target):
    cands.sort()
    res = []
    def bt(start, path, total):
        if total == target:
            res.append(list(path)); return
        for i in range(start, len(cands)):
            if total + cands[i] > target: break
            path.append(cands[i])
            bt(i, path, total + cands[i])
            path.pop()
    bt(0, [], 0)
    return res

• Combination Sum II: each candidate used at most once, input may contain duplicates.
• Combination Sum III: only digits 1-9, exactly k numbers.
• Count the number of combinations (DP) instead of enumerating them.