LeetCode 40 - Combination Sum II

LeetCode Problem 40

Difficulty: 🟡 Medium
Topics: Array, Backtracking

Solution

Problem Understanding

This problem asks us to find all unique combinations of numbers from the candidates array such that the sum of the chosen numbers equals target.

Unlike the original Combination Sum problem, each number can only be used once. Even if a number appears multiple times in the input array, each occurrence is treated as a separate element, but duplicate combinations are not allowed in the final answer.

For example, if the input is:

candidates = [1,1,2]
target = 3

then [1,2] is a valid combination, but it should only appear once in the output even though there are two 1s in the array.

The input consists of:

• candidates, an array of positive integers
• target, a positive integer representing the required sum

The output is a list of unique combinations where:

• Each combination sums to target
• Each candidate index is used at most once
• Duplicate combinations are removed

The constraints provide several important observations:

• candidates.length <= 100, which is large enough that brute-force subset generation can become expensive
• target <= 30, which is relatively small and helps pruning
• candidates[i] <= 50, meaning numbers are positive

The fact that all numbers are positive is extremely important. Once the running sum exceeds the target, we know continuing further cannot help. This allows aggressive pruning during backtracking.

Several edge cases are important:

• Duplicate numbers in the input, such as [1,1,1,2]
• Multiple ways to form the same combination
• No valid combination exists
• Single-element arrays
• Candidates larger than the target
• Repeated values that could accidentally produce duplicate answers

A naive implementation often fails because it generates the same combination multiple times in different ways.

Approaches

Brute Force Approach

The brute-force solution generates every possible subset of the candidates array and checks whether the subset sums to target.

Since each element can either be included or excluded, there are 2^n possible subsets. For every subset:

1. Compute its sum
2. If the sum equals target, add it to the answer
3. Use sorting or a set to remove duplicates

This approach is correct because it explores every possible subset, so no valid combination can be missed.

However, it is inefficient because:

• The number of subsets grows exponentially
• Duplicate combinations are generated repeatedly
• Extra work is required to deduplicate results

For n = 100, a full subset search is infeasible.

Optimal Approach, Backtracking with Sorting and Duplicate Skipping

The key insight is that we can avoid generating duplicates in the first place instead of removing them afterward.

We first sort the array. Sorting groups duplicate values together, allowing us to skip repeated numbers during the same recursive level.

The algorithm uses backtracking:

• Build combinations incrementally
• Track the remaining target
• Stop exploring once the remaining target becomes negative
• Skip duplicate numbers at the same recursive depth

The duplicate-skipping rule is the most important optimization:

if i > start and candidates[i] == candidates[i - 1]:
    continue

This means:

• At a given recursive level, only use the first occurrence of a duplicate value
• Prevent generating equivalent combinations in different orders

Because numbers are positive and sorted, we can also stop early when a candidate exceeds the remaining target.

Approach	Time Complexity	Space Complexity	Notes
Brute Force	O(2^n * n)	O(n)	Generates every subset and removes duplicates afterward
Optimal	O(2^n) in worst case	O(n) recursion depth	Uses sorting, pruning, and duplicate skipping

Algorithm Walkthrough

1. Sort the candidates array.

Sorting is essential because duplicate values become adjacent. This allows us to detect and skip duplicate combinations efficiently. 2. Create a recursive backtracking function.

The function tracks:

• The current starting index
• The remaining target
• The current combination being built

3. If the remaining target becomes zero, store the current combination.

This means we have found a valid combination whose sum equals the target. 4. Iterate through candidates starting from the current index.

We only move forward in the array so that each number is used at most once. 5. Skip duplicates at the same recursion depth.

If the current number is the same as the previous number and both are being considered at the same recursive level, skip it.

This prevents duplicate combinations. 6. Stop early if the current number exceeds the remaining target.

Since the array is sorted and all numbers are positive, every later number will also be too large. 7. Include the current number in the combination.

Add it to the current path and recursively search for the remaining sum. 8. Backtrack after recursion.

Remove the last added number so the next iteration can explore different choices.

Why it works

The algorithm systematically explores every valid combination while enforcing two important invariants:

• Elements are only chosen from later indices, ensuring each index is used once
• Duplicate values at the same recursion depth are skipped, ensuring uniqueness

Sorting guarantees that identical values appear consecutively, making duplicate detection reliable.

Python Solution

from typing import List

class Solution:
    def combinationSum2(self, candidates: List[int], target: int) -> List[List[int]]:
        candidates.sort()
        
        results = []
        current_combination = []
        
        def backtrack(start: int, remaining: int) -> None:
            if remaining == 0:
                results.append(current_combination[:])
                return
            
            for i in range(start, len(candidates)):
                # Skip duplicates at the same recursion level
                if i > start and candidates[i] == candidates[i - 1]:
                    continue
                
                # Early pruning
                if candidates[i] > remaining:
                    break
                
                current_combination.append(candidates[i])
                
                # Move to next index because each number can only be used once
                backtrack(i + 1, remaining - candidates[i])
                
                # Backtrack
                current_combination.pop()
        
        backtrack(0, target)
        
        return results

The implementation begins by sorting the input array. This enables both duplicate skipping and early pruning.

The results list stores all valid combinations, while current_combination represents the path currently being explored.

The recursive backtrack function receives:

• start, the index from which new elements may be chosen
• remaining, the remaining sum needed to reach the target

If remaining == 0, the current combination is valid and copied into the result list.

The loop iterates from start onward so that each element is used at most once. The duplicate-skipping condition ensures that identical numbers at the same recursion level are not processed multiple times.

The pruning condition:

if candidates[i] > remaining:
    break

works because the array is sorted. Once a number exceeds the remaining target, all later numbers will also exceed it.

Backtracking occurs after recursion by removing the most recently added element.

Go Solution

package main

import "sort"

func combinationSum2(candidates []int, target int) [][]int {
	sort.Ints(candidates)

	var results [][]int
	var current []int

	var backtrack func(start int, remaining int)

	backtrack = func(start int, remaining int) {
		if remaining == 0 {
			combination := make([]int, len(current))
			copy(combination, current)
			results = append(results, combination)
			return
		}

		for i := start; i < len(candidates); i++ {
			// Skip duplicates at the same recursion level
			if i > start && candidates[i] == candidates[i-1] {
				continue
			}

			// Early pruning
			if candidates[i] > remaining {
				break
			}

			current = append(current, candidates[i])

			// Move to next index
			backtrack(i+1, remaining-candidates[i])

			// Backtrack
			current = current[:len(current)-1]
		}
	}

	backtrack(0, target)

	return results
}

The Go implementation follows the same logic as the Python version.

One important difference is slice handling. In Go, slices are references to underlying arrays, so when storing a valid combination we must create a copy:

combination := make([]int, len(current))
copy(combination, current)

Without this copy, future modifications during backtracking would alter previously stored results.

Go slices are also resized during backtracking using:

current = current[:len(current)-1]

There are no integer overflow concerns because the constraints are small.

Worked Examples

Example 1

Input:

candidates = [10,1,2,7,6,1,5]
target = 8

After sorting:

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

Recursive Exploration

Step	Current Combination	Remaining	Action
1	[]	8	Start recursion
2	[1]	7	Choose first 1
3	[1,1]	6	Choose second 1
4	[1,1,2]	4	Continue
5	[1,1,5]	1	Dead end
6	[1,1,6]	0	Valid combination
7	[1,2]	5	Backtrack and try 2
8	[1,2,5]	0	Valid combination
9	[1,7]	0	Valid combination
10	[2,6]	0	Valid combination

Final result:

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

Example 2

Input:

candidates = [2,5,2,1,2]
target = 5

After sorting:

[1,2,2,2,5]

Recursive Exploration

Step	Current Combination	Remaining	Action
1	[]	5	Start
2	[1]	4	Choose 1
3	[1,2]	2	Choose first 2
4	[1,2,2]	0	Valid
5	Skip duplicate 2		Avoid duplicate path
6	[5]	0	Valid

Final result:

[
[1,2,2],
[5]
]

Complexity Analysis

Measure	Complexity	Explanation
Time	O(2^n)	Worst-case recursive subset exploration
Space	O(n)	Recursion stack and current combination

The worst-case runtime is exponential because the algorithm may need to explore many subsets of the array.

However, the practical performance is significantly improved by:

• Early pruning when sums exceed the target
• Duplicate skipping
• Sorted traversal

The auxiliary space complexity is O(n) because the recursion depth and temporary combination can each grow to at most n.

The output list itself is not included in auxiliary space complexity.

Test Cases

def normalize(result):
    return sorted([sorted(x) for x in result])

solution = Solution()

# Example 1
assert normalize(solution.combinationSum2([10,1,2,7,6,1,5], 8)) == normalize([
    [1,1,6],
    [1,2,5],
    [1,7],
    [2,6]
])  # standard example with duplicates

# Example 2
assert normalize(solution.combinationSum2([2,5,2,1,2], 5)) == normalize([
    [1,2,2],
    [5]
])  # duplicate handling

# Single element equals target
assert normalize(solution.combinationSum2([5], 5)) == normalize([
    [5]
])  # simplest valid case

# Single element does not equal target
assert normalize(solution.combinationSum2([5], 3)) == normalize([
])  # no valid combination

# Multiple duplicates
assert normalize(solution.combinationSum2([1,1,1,1], 2)) == normalize([
    [1,1]
])  # duplicate combinations should appear once

# No solution exists
assert normalize(solution.combinationSum2([3,4,5], 2)) == normalize([
])  # impossible target

# Candidates larger than target
assert normalize(solution.combinationSum2([9,10,11], 8)) == normalize([
])  # pruning behavior

# Multiple valid combinations
assert normalize(solution.combinationSum2([1,2,3,4,5], 5)) == normalize([
    [1,4],
    [2,3],
    [5]
])  # several valid answers

# Repeated values with multiple paths
assert normalize(solution.combinationSum2([2,2,2,2], 4)) == normalize([
    [2,2]
])  # avoid duplicate outputs

# Larger mixed input
assert normalize(solution.combinationSum2([1,1,2,2,3,3], 6)) == normalize([
    [1,1,2,2],
    [1,2,3],
    [3,3]
])  # complex duplicate interactions

Test	Why
[10,1,2,7,6,1,5], 8	Standard example with duplicates
[2,5,2,1,2], 5	Verifies duplicate skipping
[5], 5	Single valid element
[5], 3	Single invalid element
[1,1,1,1], 2	Heavy duplicate handling
[3,4,5], 2	No possible solution
[9,10,11], 8	Tests pruning
[1,2,3,4,5], 5	Multiple valid combinations
[2,2,2,2], 4	Duplicate outputs prevention
[1,1,2,2,3,3], 6	Complex recursive branching

Edge Cases

One important edge case occurs when the input contains many duplicate values. For example:

[1,1,1,1]

with target 2.

A naive backtracking solution may generate [1,1] multiple times from different indices. The implementation handles this correctly using:

if i > start and candidates[i] == candidates[i - 1]:
    continue

This ensures duplicates are skipped only at the same recursion depth.

Another important edge case occurs when no valid combination exists. For example:

candidates = [5,6,7]
target = 3

Since all numbers exceed the target, the algorithm immediately prunes recursion after sorting. The result remains empty.

A third edge case occurs when a candidate exactly equals the remaining target. For example:

candidates = [1,2,5]
target = 5

The algorithm correctly recognizes [5] as a complete solution because the base case checks:

if remaining == 0:

immediately after subtraction.

A final subtle edge case involves ensuring elements are not reused. In this problem, each candidate may only be used once. The implementation guarantees this by calling recursion with:

backtrack(i + 1, ...)

instead of:

backtrack(i, ...)

This forces future recursive calls to move forward in the array, preventing reuse of the same index.