Problem Description

You are given an array of distinct integers called candidates and a target integer target. Your task is to find all unique combinations of numbers from candidates that sum up to target.

Key points about this problem:

1. Numbers can be reused: You can use the same number from candidates multiple times in a single combination. For example, if candidates = [2, 3, 5] and target = 8, then [2, 2, 2, 2] is a valid combination.

2. All numbers are distinct: The candidates array contains no duplicate values.

3. Unique combinations: Two combinations are considered different if at least one number appears a different number of times. For example, [2, 2, 3] and [2, 3, 3] are different combinations.

4. Order doesn't matter: [2, 3] and [3, 2] are considered the same combination, so you should only include one of them in your result.

5. Return format: Return a list of lists, where each inner list represents one valid combination. The combinations can be returned in any order.

For example:

• If candidates = [2, 3, 6, 7] and target = 7, the output would be [[2, 2, 3], [7]]
  • [2, 2, 3] sums to 7 (using 2 twice and 3 once)
  • [7] sums to 7 (using 7 once)

The problem guarantees that the number of unique combinations will be less than 150 for any given input.

Flowchart Walkthrough

First, let's pin down the algorithm using the Flowchart. Here's a step-by-step walkthrough:

Is it a graph?

• No: The problem involves finding combinations from an array that sum to a target value. This is not about nodes and edges or graph traversal.

Need to solve for kth smallest/largest?

• No: We're not looking for the kth smallest or largest element. We need to find all valid combinations that sum to the target.

Involves Linked Lists?

• No: The problem works with an array of integers, not linked lists.

Does the problem have small constraints?

• Yes: The problem statement explicitly mentions that the number of unique combinations is less than 150 for any given input. This is a relatively small constraint, suggesting that exploring all possibilities is feasible.

Brute force / Backtracking?

• Yes: Since we need to find all possible combinations and the constraints are small, backtracking is the appropriate approach. We need to explore different combinations by:
  • Including an element (potentially multiple times)
  • Backtracking when the sum exceeds the target
  • Recording valid combinations when the sum equals the target
  • Trying different elements at each decision point

Conclusion: The flowchart correctly leads us to use a Backtracking approach. This makes sense because we need to systematically explore all possible combinations of numbers that can sum to the target, with the ability to reuse numbers and backtrack when a path doesn't lead to a valid solution.

Intuition

Think of this problem like making change with coins, but you have unlimited coins of each denomination and need to find all possible ways to make the exact amount.

The key insight is that at each step, we face a decision: which number should we try next? Since we can reuse numbers, after picking a number, we have the same set of choices available again. This naturally leads to a recursive approach where we:

1. Pick a number from the available candidates
2. Subtract it from our remaining target
3. Recursively solve for the new remaining target

The beauty of backtracking here is that it allows us to explore all paths systematically. When we pick a number like 2 from [2, 3, 6, 7] to reach target 7, we continue using 2 until either:

• We reach exactly 7 (found a valid combination!)
• We exceed 7 (this path won't work, backtrack)
• We realize we can't reach 7 with the current path

To avoid duplicate combinations like [2, 3] and [3, 2], we use a clever trick: always pick numbers in non-decreasing order. We do this by maintaining an index i that tells us the minimum position in the candidates array we can pick from. If we picked candidates[3], our next pick must be from index 3 or later, never from indices 0, 1, or 2.

Sorting the candidates array first gives us an additional optimization. If the smallest available candidate is already larger than our remaining target, we know that all subsequent candidates will also be too large (since the array is sorted). This allows us to prune entire branches of our search tree early, significantly improving performance.

The recursive nature of the problem becomes clear when you realize that after picking a number and subtracting it from the target, you're left with the exact same type of problem - just with a smaller target value. This self-similar structure is what makes backtracking with recursion such an elegant solution.

Learn more about Backtracking patterns.

Solution Approach

The implementation uses a Depth-First Search (DFS) with backtracking approach. Let's walk through the key components:

1. Sorting for Optimization

candidates.sort()

We first sort the candidates array. This enables early termination when we encounter a candidate larger than the remaining target, as all subsequent candidates will also be too large.

2. DFS Function Design

The core logic is in the dfs(i, s) function where:

• i: The starting index in the candidates array (ensures we don't create duplicate combinations)
• s: The remaining sum we need to reach

3. Base Cases

if s == 0:
    ans.append(t[:])
    return
if s < candidates[i]:
    return

• Success case: When s == 0, we've found a valid combination. We add a copy of the current path t[:] to our answer.
• Pruning case: When s < candidates[i], the smallest available candidate is too large, so we can stop exploring this branch.

4. Backtracking Logic

for j in range(i, len(candidates)):
    t.append(candidates[j])
    dfs(j, s - candidates[j])
    t.pop()

This is the heart of the backtracking algorithm:

• Iterate from index i: This ensures we only consider candidates at position i or later, preventing duplicates
• Make a choice: Add candidates[j] to our current path t
• Explore: Recursively call dfs(j, s - candidates[j]). Note we pass j (not j+1) because we can reuse the same number
• Backtrack: Remove the last element with t.pop() to try other possibilities

5. Data Structures

• t = []: A temporary list that maintains the current combination being built
• ans = []: Stores all valid combinations found

Why This Works

The algorithm systematically explores all possible combinations:

1. For each candidate, it tries using it 0, 1, 2, ... times until the sum exceeds the target
2. By starting each recursive call from index i or later, we ensure combinations like [2,3] and [3,2] aren't both generated
3. The sorting optimization allows us to stop early when we know no valid combinations can be formed

Time Complexity Analysis

• In the worst case, we might explore O(2^n) combinations (where each element can be included or not)
• For each valid combination, we need O(n) time to copy it to the answer
• Overall: O(2^n × n), though pruning significantly reduces the actual runtime

Space Complexity

• The recursion depth can go up to target/min(candidates) in the worst case
• We also store the temporary path t which can have at most target/min(candidates) elements
• Overall: O(n) where n is the maximum depth of recursion

Example Walkthrough

Let's trace through the algorithm with candidates = [2, 3, 5] and target = 8.

Initial Setup:

• Sort candidates: [2, 3, 5] (already sorted)
• Start with empty path t = [] and call dfs(0, 8)

Execution Tree:

dfs(0, 8) - Can use candidates from index 0 onwards
├─ Choose 2: t = [2], dfs(0, 6)
│  ├─ Choose 2: t = [2,2], dfs(0, 4)
│  │  ├─ Choose 2: t = [2,2,2], dfs(0, 2)
│  │  │  ├─ Choose 2: t = [2,2,2,2], dfs(0, 0) ✓ Found [2,2,2,2]
│  │  │  ├─ Choose 3: t = [2,2,2,3], dfs(1, -1) ✗ (negative sum)
│  │  │  └─ Choose 5: t = [2,2,2,5], dfs(2, -3) ✗ (negative sum)
│  │  ├─ Choose 3: t = [2,2,3], dfs(1, 1)
│  │  │  └─ 1 < 3, return ✗ (remaining sum too small)
│  │  └─ Choose 5: t = [2,2,5], dfs(2, -1) ✗ (negative sum)
│  ├─ Choose 3: t = [2,3], dfs(1, 3)
│  │  ├─ Choose 3: t = [2,3,3], dfs(1, 0) ✓ Found [2,3,3]
│  │  └─ Choose 5: t = [2,3,5], dfs(2, -2) ✗ (negative sum)
│  └─ Choose 5: t = [2,5], dfs(2, 1)
│     └─ 1 < 5, return ✗ (remaining sum too small)
├─ Choose 3: t = [3], dfs(1, 5)
│  ├─ Choose 3: t = [3,3], dfs(1, 2)
│  │  └─ 2 < 3, return ✗ (remaining sum too small)
│  └─ Choose 5: t = [3,5], dfs(2, 0) ✓ Found [3,5]
└─ Choose 5: t = [5], dfs(2, 3)
   └─ 3 < 5, return ✗ (remaining sum too small)

Step-by-step for finding [2,2,2,2]:

1. Start with dfs(0, 8), choose candidates[0] = 2, add to path: t = [2]
2. Call dfs(0, 6), choose candidates[0] = 2 again, add to path: t = [2,2]
3. Call dfs(0, 4), choose candidates[0] = 2 again, add to path: t = [2,2,2]
4. Call dfs(0, 2), choose candidates[0] = 2 again, add to path: t = [2,2,2,2]
5. Call dfs(0, 0), sum is 0 - we found a valid combination! Add [2,2,2,2] to answer
6. Backtrack by popping elements and trying other branches

Key Observations:

• When we choose index j, the next recursive call uses j (not j+1) as the starting index, allowing number reuse
• The algorithm avoids duplicates like [3,2,3] because once we choose 3 at index 1, we can't go back to choose 2 at index 0
• Early termination happens when remaining sum is less than the smallest available candidate

Final Result: [[2,2,2,2], [2,3,3], [3,5]]

Solution Implementation

Time and Space Complexity

Time Complexity: O(N^(T/M)) where N is the number of candidates, T is the target value, and M is the minimal value among the candidates.

The analysis breaks down as follows:

• In the worst case, the recursion tree can have a maximum depth of T/M (when we keep choosing the smallest element repeatedly until we reach the target).
• At each level of recursion, we can branch out to at most N different candidates (the for loop iterates through all candidates from index i to the end).
• The number of nodes in the recursion tree represents the number of recursive calls, which is bounded by N^(T/M).
• At each leaf node where we find a valid combination (s == 0), we append a copy of the current path to the answer, which takes O(T/M) time in the worst case.
• However, the number of valid combinations is typically much smaller than the total number of nodes, so the dominant factor remains O(N^(T/M)).

Space Complexity: O(T/M)

The space complexity consists of:

• Recursion stack depth: The maximum depth of the recursion is T/M (when we repeatedly choose the minimum value), requiring O(T/M) space for the call stack.
• Temporary list t: This list stores the current combination being built and can have at most T/M elements, requiring O(T/M) space.
• Output space: The space for storing the final answer ans is not counted as part of the auxiliary space complexity as it's required for the output.

Note that sorting the candidates takes O(N log N) time but only O(1) or O(log N) auxiliary space depending on the sorting algorithm used, which doesn't affect the overall space complexity dominated by the recursion depth.

Learn more about how to find time and space complexity quickly.

Common Pitfalls

1. Creating Duplicate Combinations by Not Maintaining Start Index

The Pitfall: A common mistake is to iterate through ALL candidates in each recursive call instead of starting from the current index. This leads to duplicate combinations in different orders.

Incorrect Implementation:

def backtrack(remaining_sum):
    if remaining_sum == 0:
        result.append(current_combination[:])
        return
  
    # WRONG: Starting from 0 every time creates duplicates
    for i in range(len(candidates)):  
        if candidates[i] <= remaining_sum:
            current_combination.append(candidates[i])
            backtrack(remaining_sum - candidates[i])
            current_combination.pop()

Why it's wrong: This would generate both [2, 3] and [3, 2] as separate combinations when target = 5 and candidates = [2, 3].

The Fix: Always pass and use a start_index parameter to ensure you only consider candidates from the current position onwards:

def backtrack(start_index, remaining_sum):
    # ... base cases ...
  
    # Correct: Start from start_index to avoid duplicates
    for i in range(start_index, len(candidates)):
        current_combination.append(candidates[i])
        backtrack(i, remaining_sum - candidates[i])  # Pass i, not i+1
        current_combination.pop()

2. Forgetting to Copy the List When Adding to Results

The Pitfall: Appending the reference to current_combination instead of a copy means all results will point to the same list object, which gets modified throughout the recursion.

Incorrect Implementation:

if remaining_sum == 0:
    result.append(current_combination)  # WRONG: Appends reference
    return

Why it's wrong: Since current_combination is modified during backtracking, all entries in result will end up being empty lists or containing the same final state.

The Fix: Always create a copy of the current combination when adding it to results:

if remaining_sum == 0:
    result.append(current_combination[:])  # Correct: Creates a copy
    # Or use: result.append(list(current_combination))
    return

3. Incorrect Pruning Logic After Sorting

The Pitfall: When implementing the optimization with sorted candidates, accessing candidates[start_index] without checking bounds can cause an IndexError.

Incorrect Implementation:

def backtrack(start_index, remaining_sum):
    if remaining_sum == 0:
        result.append(current_combination[:])
        return
  
    # WRONG: No bounds checking before accessing candidates[start_index]
    if remaining_sum < candidates[start_index]:  
        return

Why it's wrong: If start_index >= len(candidates), this will throw an IndexError.

The Fix: Add proper bounds checking:

def backtrack(start_index, remaining_sum):
    if remaining_sum == 0:
        result.append(current_combination[:])
        return
  
    # Correct: Check bounds first
    if start_index >= len(candidates) or remaining_sum < candidates[start_index]:
        return

4. Using i+1 Instead of i in Recursive Call

The Pitfall: Passing i+1 instead of i to the recursive call prevents reusing the same number multiple times.

Incorrect Implementation:

for i in range(start_index, len(candidates)):
    current_combination.append(candidates[i])
    backtrack(i + 1, remaining_sum - candidates[i])  # WRONG: Can't reuse numbers
    current_combination.pop()

Why it's wrong: This would make it impossible to generate combinations like [2, 2, 3] where a number appears multiple times.

The Fix: Pass i (not i+1) to allow reusing the same candidate:

for i in range(start_index, len(candidates)):
    current_combination.append(candidates[i])
    backtrack(i, remaining_sum - candidates[i])  # Correct: Allows reuse
    current_combination.pop()