Generated by Codex with GPT-5

Quick facts

What the problem is really asking

The input gives a set of distinct candidate numbers and a target. The task is to return every unique combination of candidates whose sum is exactly the target.

Two details define the real problem:

  • A number can be reused as many times as needed.
  • Combinations are considered the same if they use the same values with the same counts, even if the order is different.

So this is not a permutation problem. It is a controlled search problem: explore all ways to build the target sum while avoiding duplicate orderings like [2, 3, 3] and [3, 2, 3].

The key insight

The clean way to avoid duplicates is to make a choice about order up front:

build each combination in non-decreasing candidate order.

That means once the search decides to use candidate 3, it should never go backward and later insert 2. Each recursive call carries a start_index, and the next choice can only come from that index or later. Reusing the same number is still allowed, so the recursive call for “take this number” stays at the same index instead of moving to the next one.

Sorting the candidates gives one more useful property: as soon as a candidate is larger than the remaining target, every candidate after it is also too large, so that entire branch can stop immediately.

How to derive the optimal solution in an interview

A good derivation usually looks like this:

First, try the direct recursive framing: for each position, either take a candidate or skip it. That quickly reveals two problems: there are many repeated states, and naive recursion generates duplicates because the same values can appear in different orders.

Next, focus on the duplicate issue. The natural fix is to force combinations to grow in one direction only. That turns “all orders” into “one canonical order per combination,” which removes duplicates without needing a set of tuples or any post-processing.

Then notice that the target only decreases. Once the remaining target becomes negative, that branch is impossible. If the candidates are sorted, there is an even stronger pruning rule: when the current candidate is already bigger than the remaining target, the loop can stop immediately.

That leads to the standard backtracking pattern:

  1. Keep a running combination.
  2. Keep the remaining target.
  3. Iterate candidates from start_index forward.
  4. Recurse with the same index to allow reuse.
  5. Pop the last choice to backtrack and try the next one.

Why this solution works

The algorithm is complete because it explores every valid count of every candidate in non-decreasing order. If a solution exists, there is exactly one path in the search tree that builds it.

The algorithm is duplicate-free because each recursive level only chooses from the current index onward. That means a combination like [2, 2, 3] can be built, but [3, 2, 2] cannot, so the same multiset is never emitted twice.

The pruning is also safe. If candidate > remaining_target, then any later candidate is at least as large, so none of them can fit either. Stopping there cannot hide a valid solution.

Best approach

Backtracking with sorted candidates is the standard optimal answer for this problem.

  • Time: output-sensitive and exponential in the worst case, because the algorithm may need to enumerate many valid combinations.
  • Space: O(target / min(candidates)) recursion depth in the worst case for the search stack, plus the space needed to store the output combinations.

For interview purposes, the important point is not the exact closed-form bound. What matters is understanding that this is a combinatorial enumeration problem, so the runtime is dominated by the number of valid branches and returned answers.

Python solution

The implementation below keeps the recursive search small and explicit:

  • sorted_candidates enables pruning.
  • current_combination holds the path currently being explored.
  • start_index prevents duplicate orderings.
  • The helper appends a copy of the current path only when the remaining target reaches zero.
from typing import List


def build_combinations_that_sum_to_target(
    candidates: List[int], target: int
) -> List[List[int]]:
    """
    Return all unique combinations of candidates that sum to target.

    Each candidate may be reused any number of times.
    """
    sorted_candidates = sorted(candidates)
    combinations: List[List[int]] = []
    current_combination: List[int] = []

    def search(start_index: int, remaining_target: int) -> None:
        # A remaining target of zero means the current path is a full solution.
        if remaining_target == 0:
            combinations.append(list(current_combination))
            return

        for candidate_index in range(start_index, len(sorted_candidates)):
            candidate_value = sorted_candidates[candidate_index]

            # Because the candidates are sorted, no later candidate can fit either.
            if candidate_value > remaining_target:
                break

            current_combination.append(candidate_value)

            # Reuse is allowed, so the next search starts at the same index.
            search(candidate_index, remaining_target - candidate_value)

            # Restore the path before trying the next candidate.
            current_combination.pop()

    search(start_index=0, remaining_target=target)
    return combinations


class Solution:
    def combinationSum(self, candidates: List[int], target: int) -> List[List[int]]:
        """LeetCode entry point."""
        return build_combinations_that_sum_to_target(candidates, target)

Interview follow-ups

What changes if each number can be used at most once?

That becomes the Combination Sum II shape. The search is still backtracking, but the recursive call moves to candidate_index + 1 instead of staying at candidate_index, because reuse is no longer allowed. The harder part is duplicate handling: if the input can contain repeated values, the loop must skip equal candidates at the same recursion depth so the same combination is not produced multiple times. The approach still works because sorting groups duplicates together and gives a consistent way to decide which copy is allowed to start a branch. The runtime remains exponential in the worst case, but the branching factor is often smaller because reuse is removed.

Could dynamic programming solve this problem too?

Yes, but it is usually less natural if the goal is to return the actual combinations. A DP solution can store, for each intermediate sum, the combinations that reach that sum, then extend them with later candidates. That can work, but it tends to be heavier in both code and memory because the state must carry large lists of partial combinations. Backtracking is usually preferred because it builds one path at a time, prunes early, and maps directly to the way the problem is stated. DP becomes more attractive when the interviewer changes the problem to “count the number of combinations” rather than “return them.”

Why do we sort if the original problem does not ask for sorted output?

Sorting is not for presentation. It is for control of the search space. Once the candidates are sorted, the algorithm gets two benefits that materially simplify the solution: it can stop the loop early when a candidate is too large, and it can enforce a non-decreasing construction order that removes duplicate permutations. Without sorting, the algorithm would either waste work exploring impossible large values or need extra machinery to deduplicate results after the fact. The asymptotic worst-case complexity stays exponential either way, but sorting makes the search far cleaner and usually much faster in practice.

How would you count combinations instead of returning them?

If only the count is needed, the problem becomes much cheaper in memory because the algorithm no longer has to store every path explicitly. One option is to keep the same backtracking structure and increment a counter whenever the remaining target reaches zero. Another option is a DP formulation where dp[sum] represents how many ways to build that sum using candidates processed so far. The DP version is often the better answer for the counting variant because it reuses overlapping subproblems instead of materializing every combination. The tradeoff is that DP gives counts efficiently, but it does not directly recover the actual combination lists without storing much more information.