We're given an array of distinct positive integers and a target sum. We need to find every way to pick numbers from the array (with unlimited reuse) that add up exactly to the target. The order of numbers in a combination doesn't matter, so [2, 2, 3] and [2, 3, 2] are the same combination and should only appear once.

Unlike problems where each element can be used at most once, the same candidate can appear in a combination any number of times. That makes the search space large, but the constraints (target at most 40, every candidate at least 2) keep it small enough to enumerate.

This is a backtracking problem. We explore all ways to build up to the target by trying each candidate and recursing with the remaining sum. To avoid duplicate combinations, we enforce an ordering: once we move past a candidate, we never go back to it.

Key Constraints:

Intuition

For each candidate, decide how many times to include it (0, 1, 2, ... up to target / candidate), then move on to the next candidate. After a decision has been made for every candidate, check if the total sum equals the target.

This enumerates every possible "frequency vector." With candidates [2, 3, 7] and target 7, we try (0 twos, 0 threes, 0 sevens), (1 two, 0 threes, 0 sevens), ..., (3 twos, 0 threes, 0 sevens), (0 twos, 1 three, 0 sevens), and so on. Most of these overshoot the target or fall short, but we check every possibility.

This approach prunes nothing beyond capping each count so the running sum stays within the target. It generates all frequency assignments and only filters valid ones at the end. Duplicates are impossible by construction: a combination is determined by how many copies of each candidate it contains, and each frequency vector is visited once.

Algorithm

Example Walkthrough

The trace below uses candidates = [2, 3, 6, 7] and target = 7. Counts are tried in ascending order, so the branch with zero copies of everything except one 7 is explored first, and [7] is found before [2, 2, 3].

Code

This approach commits to a full count for each candidate before it can tell whether the branch is feasible. The next approach makes one decision at a time and abandons a branch as soon as the remaining target can no longer be reached.

Intuition

Instead of deciding how many times to use each candidate upfront, backtracking makes one decision at a time: pick one candidate, subtract it from the target, and recurse with the reduced target. If the remaining target reaches zero, we found a valid combination. If a candidate exceeds the remaining target, we stop extending that branch and backtrack.

Duplicates are avoided with a start index. When we pick the candidate at index i, the recursive call considers only candidates at index i or later. We never pick candidate[2] after candidate[3], so [3, 2] is never generated as a separate combination from [2, 3].

Sorting the candidates first enables one more pruning step. If the current candidate exceeds the remaining target, every later candidate does too (the array is in ascending order), so the loop can break immediately instead of checking each one.

Algorithm

Example Walkthrough

The same input, traced with the pruned backtracking. Each recursive call resumes its loop at the index of the last pick, and a branch ends as soon as the next candidate exceeds the remaining target.

Code