39. Combination Sum

Summary

Return a list of all unique combinations of candidates where the chosen numbers sum to target.

The same number may be chosen from candidates an unlimited number of times. Two combinations are unique if at least one chosen number is different.

The test cases are generated such that the number of unique combinations that sum to target is less than 150.

Approach

Backtracking. Reuse the same number repeatedly until the running total exceeds target.

The number of valid combinations is at most 150 in this problem, so exploring combinations recursively is feasible.

Function

Initialization:

ans: list of combinations whose sum equals target.

Recursive call:

arguments: start_idx, remains, current combination path.

If remains == 0, we found a valid combination. Add a deep copy of path to ans. If remains < 0, return.

For each index i and value n in candidates[start_idx:]: append n to path recurse with (start_idx + i, remains - n, path) pop n from path

We use start_idx to avoid duplicates. Without start_idx:

candidates = [1,2,3]

pattern 1: [1,1,2,...] pattern 2: [2,1,1,...]

These represent the same combination but appear in different orders. With start_idx, we only build combinations in non-decreasing index order.

Complexity

Time Complexity: O(N^(T/M + 1)), where N is the number of candidates, M is the minimum value in candidates, and T is target.

The total number of nodes in an N-ary tree of height h is:

1 + N + ... + N^h = (N^(h+1) - 1) / (N - 1)

So the order is O(N^(h+1)), and since h = T/M, this becomes O(N^(T/M + 1)).

At each leaf node, we also pay a copy cost of about O(T/M), which is dominated by the tree size in this bound.

Space Complexity: O(T/M) for the recursion stack and current combination path.