Problem Description

You are given an array of candidate numbers (candidates) and a target number (target). Your task is to find all unique combinations of numbers from candidates that sum up to the target.

The key constraints are:

• Each number in candidates can only be used once in each combination
• The solution set must not contain duplicate combinations

For example, if candidates = [10, 1, 2, 7, 6, 1, 5] and target = 8, the valid combinations would be:

• [1, 1, 6]
• [1, 2, 5]
• [1, 7]
• [2, 6]

Note that even though the array might contain duplicate values (like two 1's in the example), each element at a specific index can only be used once. However, if there are multiple occurrences of the same value, they can appear together in a combination (like [1, 1, 6] using both 1's from different positions).

The challenge involves:

1. Finding all valid combinations that sum to the target
2. Ensuring each element is used at most once
3. Avoiding duplicate combinations in the result set

This is a classic backtracking problem where you need to explore all possible combinations while pruning invalid paths and handling duplicates appropriately.

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 candidates, not linked lists.

Does the problem have small constraints?

• Yes: This is a combination problem where we need to explore all possible combinations. The nature of finding all unique combinations suggests that the constraints would be reasonably small (typical constraints for such problems are array length ≤ 100 and values ≤ 50), as the number of combinations can grow exponentially.

Brute force / Backtracking?

• Yes: We need to systematically explore all possible combinations by:
  • Including or excluding each element
  • Tracking the current sum
  • Backtracking when we exceed the target or complete a valid combination
  • Handling duplicates to ensure unique combinations

Conclusion: The flowchart correctly leads us to use a Backtracking approach. This makes sense because we need to:

1. Explore all possible combinations systematically
2. Build combinations incrementally
3. Abandon paths that exceed the target (pruning)
4. Backtrack to try different combinations
5. Handle duplicate elements to avoid duplicate combinations in the result

Intuition

When we need to find all combinations that sum to a target, we're essentially building subsets of the array where each subset's sum equals the target. Since we need all valid combinations, we must explore every possibility systematically - this naturally leads to a backtracking approach.

The key insight is that at each step, we have a choice: include the current element or skip it. If we include it, we reduce our remaining target by that element's value and move forward. If we skip it, we simply move to the next element. This creates a decision tree where each path represents a potential combination.

However, there are two main challenges to address:

1. Avoiding duplicate combinations: Since the array might contain duplicate values, we could end up with identical combinations through different paths. For example, if we have [1, 1, 2] and target 3, we might get [1, 2] twice using different 1s. To solve this, we first sort the array. Then, when we're at the same recursion level (same position in our decision-making), we skip over duplicate values after using them once. This ensures we don't create the same combination multiple times.

2. Efficient pruning: Since we sorted the array, if our current element is already larger than the remaining target, all subsequent elements will also be too large (they're equal or greater). We can immediately stop exploring this path, significantly reducing unnecessary computations.

The backtracking pattern emerges naturally: we build our combination step by step, adding elements to our current path (t). When we reach our target sum (success!) or determine we can't proceed (too large or out of elements), we backtrack by removing the last added element and trying the next possibility. This systematic exploration with pruning ensures we find all valid combinations efficiently without repetition.

Learn more about Backtracking patterns.

Solution Approach

The implementation follows a sorting + pruning + backtracking strategy. Let's walk through how the solution works:

1. Initial Setup and Sorting

First, we sort the candidates array. This serves two crucial purposes:

• It allows us to skip duplicate values efficiently
• It enables early termination when elements become too large

candidates.sort()
ans = []  # stores all valid combinations
t = []    # current path/combination being built

2. The DFS Function Design

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

• i represents the current index in the candidates array
• s represents the remaining target sum we need to achieve

3. Base Cases

if s == 0:
    ans.append(t[:])  # Found valid combination, add copy to answer
    return
if i >= len(candidates) or s < candidates[i]:
    return  # Out of bounds or current element too large

When s == 0, we've found a valid combination. We append a copy of the current path t[:] to our answer.

When i >= len(candidates) or s < candidates[i], we can't proceed further. The second condition is our pruning optimization - since the array is sorted, if the current element is larger than the remaining sum, all subsequent elements will also be too large.

4. Exploration with Duplicate Handling

for j in range(i, len(candidates)):
    if j > i and candidates[j] == candidates[j - 1]:
        continue  # Skip duplicates at the same recursion level
    t.append(candidates[j])
    dfs(j + 1, s - candidates[j])
    t.pop()

The loop explores all possibilities starting from index i. The critical duplicate-handling logic is:

• j > i and candidates[j] == candidates[j - 1]: This condition ensures we skip duplicate values at the same recursion level
• When j == i, we're using the first occurrence of a value, which is allowed
• When j > i and the current value equals the previous one, we skip it because we've already explored combinations starting with that value

5. Backtracking Pattern

The backtracking happens through:

1. Add: t.append(candidates[j]) - add current element to path
2. Explore: dfs(j + 1, s - candidates[j]) - recursively explore with updated index and remaining sum
3. Remove: t.pop() - remove the element to try next possibility

Note that we pass j + 1 (not i + 1) to ensure each element is used only once.

Time and Space Complexity

• Time Complexity: O(2^n × n) in the worst case, where n is the length of candidates. Each element has two choices (include/exclude), and we might need to copy paths of length up to n. However, pruning significantly reduces the actual time.
• Space Complexity: O(n) for the recursion stack and temporary path storage.

The elegance of this solution lies in how sorting enables both duplicate handling and pruning, while the backtracking pattern systematically explores all valid combinations without repetition.

Example Walkthrough

Let's trace through a small example with candidates = [2, 1, 2, 1] and target = 3.

Step 1: Sort the array After sorting: candidates = [1, 1, 2, 2]

Step 2: Start DFS exploration

We'll track the recursion tree, where each call is dfs(i, s) with current path t:

Initial: dfs(0, 3), t = []
│
├─ j=0: Choose candidates[0]=1
│  dfs(1, 2), t = [1]
│  │
│  ├─ j=1: Choose candidates[1]=1
│  │  dfs(2, 1), t = [1, 1]
│  │  │
│  │  ├─ j=2: Choose candidates[2]=2
│  │  │  dfs(3, -1), t = [1, 1, 2]
│  │  │  s < 0, backtrack
│  │  │
│  │  └─ j=3: s=1 < candidates[3]=2
│  │     Skip (pruning)
│  │  
│  ├─ j=2: Choose candidates[2]=2
│  │  dfs(3, 0), t = [1, 2]
│  │  s = 0! Found combination [1, 2] ✓
│  │
│  └─ j=3: Skip (duplicate of candidates[2])
│
├─ j=1: Skip (duplicate of candidates[0] at same level)
│
├─ j=2: Choose candidates[2]=2
│  dfs(3, 1), t = [2]
│  │
│  └─ j=3: Choose candidates[3]=2
│     dfs(4, -1), t = [2, 2]
│     s < 0, backtrack
│
└─ j=3: Skip (duplicate of candidates[2] at same level)

Key observations from the walkthrough:

1. Duplicate handling: At the root level, we skip j=1 because candidates[1]=1 equals candidates[0]=1. Similarly, we skip j=3 because it equals candidates[2]=2.

2. Different recursion levels: Inside the first branch (after choosing candidates[0]=1), we CAN choose candidates[1]=1 because it's at a different recursion level (j=i condition).

3. Pruning: When exploring [1, 1] with remaining sum 1, we skip candidates[3]=2 because it's larger than our remaining target.

4. Backtracking: After finding [1, 2], we backtrack (pop 2, then pop 1) to explore other possibilities.

Final Result: [[1, 2]]

This example demonstrates how the algorithm:

• Uses sorting to group duplicates together
• Skips duplicates at the same recursion level to avoid duplicate combinations
• Prunes branches early when elements are too large
• Systematically explores all valid paths through backtracking

Solution Implementation

Time and Space Complexity

Time Complexity: O(2^n)

The algorithm explores all possible combinations of candidates. In the worst case where all elements can be used and the target is large, we might explore nearly all subsets of the candidates array. For each element, we have two choices: include it or skip it. However, due to pruning (when s < candidates[i] or duplicates are skipped), the actual number of recursive calls is reduced, but the upper bound remains O(2^n) where n is the length of the candidates array.

Additionally, sorting the array takes O(n log n) time. Since O(2^n) dominates O(n log n), the overall time complexity is O(2^n).

Space Complexity: O(n)

The space complexity consists of:

• Recursion stack: The maximum depth of the recursion tree is O(n) in the worst case when we include all elements one by one.
• Temporary array t: This array stores the current combination being built and can have at most n elements.
• Output array ans: While this stores all valid combinations, it's typically not counted in space complexity analysis as it's part of the required output.

Therefore, the space complexity is O(n) for the recursion stack and temporary storage, where n is the length of the candidates array.

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

Common Pitfalls

1. Incorrect Duplicate Handling - Using Wrong Index Comparison

One of the most common mistakes is incorrectly handling duplicates by using the wrong condition for skipping duplicate elements.

Incorrect Implementation:

# WRONG: This skips ALL duplicates, even valid ones
for idx in range(start_index, len(candidates)):
    if idx > 0 and candidates[idx] == candidates[idx - 1]:  # Bug: idx > 0
        continue

The Problem: Using idx > 0 instead of idx > start_index will skip duplicates across different recursion levels. This causes valid combinations to be missed. For example, with candidates = [1, 1, 2] and target = 3, the combination [1, 1, 1] would be incorrectly skipped.

Correct Implementation:

for idx in range(start_index, len(candidates)):
    if idx > start_index and candidates[idx] == candidates[idx - 1]:
        continue

The key insight is that we only want to skip duplicates within the same recursion level, not across different levels.

2. Forgetting to Sort the Array

Incorrect Implementation:

def combinationSum2(self, candidates, target):
    # WRONG: Forgot to sort
    # candidates.sort()  <- Missing this line
    result = []
    current_combination = []
    backtrack(0, target)
    return result

The Problem: Without sorting:

• The duplicate-skipping logic fails (adjacent duplicates might not be detected)
• The pruning optimization remaining_sum < candidates[start_index] becomes ineffective
• You might get duplicate combinations in the result

Solution: Always sort the candidates array before starting the backtracking process.

3. Using the Same Element Multiple Times

Incorrect Implementation:

def backtrack(start_index, remaining_sum):
    for idx in range(start_index, len(candidates)):
        current_combination.append(candidates[idx])
        # WRONG: Passing idx instead of idx + 1
        backtrack(idx, remaining_sum - candidates[idx])  # Bug: should be idx + 1
        current_combination.pop()

The Problem: Passing idx instead of idx + 1 allows the same element to be used multiple times, which violates the problem constraint. This would turn it into a "Combination Sum I" problem where elements can be reused.

Correct Implementation:

backtrack(idx + 1, remaining_sum - candidates[idx])

4. Appending Reference Instead of Copy

Incorrect Implementation:

if remaining_sum == 0:
    # WRONG: Appending reference to the mutable list
    result.append(current_combination)  # Bug: should be current_combination[:]
    return

The Problem: Python lists are mutable objects. Appending current_combination directly adds a reference to the same list object that continues to be modified during backtracking. This results in the final answer containing multiple references to the same (empty) list.

Correct Implementation:

if remaining_sum == 0:
    result.append(current_combination[:])  # Create a copy
    return

5. Missing Early Termination Optimization

Suboptimal Implementation:

def backtrack(start_index, remaining_sum):
    if remaining_sum == 0:
        result.append(current_combination[:])
        return
    if start_index >= len(candidates):  # Missing the pruning condition
        return
  
    for idx in range(start_index, len(candidates)):
        # No check if candidates[idx] > remaining_sum
        current_combination.append(candidates[idx])
        backtrack(idx + 1, remaining_sum - candidates[idx])
        current_combination.pop()

The Problem: Without checking remaining_sum < candidates[start_index], the algorithm explores branches that cannot possibly lead to valid solutions. Since the array is sorted, if the current smallest available element is larger than the remaining sum, all subsequent elements will also be too large.

Optimized Implementation:

if start_index >= len(candidates) or remaining_sum < candidates[start_index]:
    return

This pruning can significantly reduce the search space and improve performance, especially for large inputs with many elements greater than the target.