LeetCode · #40

Combination Sum II Solution

Find all unique combinations where each number may be used at most once and the sum equals target.

Section One · Problem

Problem Statement

🏷️

Difficulty

Medium

🔗

LeetCode

Problem #40

🏗️

Pattern

Backtracking — sort + no reuse + dedup

Compared with LC 39, there are two key differences: the input may contain duplicates, and each element can be used only once. That changes the recursive step from i to i + 1 and requires duplicate skipping at the same recursion level.

Example

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

Constraints

• 1 ≤ candidates.length ≤ 100 • 1 ≤ candidates[i] ≤ 50 • 1 ≤ target ≤ 30

Section Two · Approach 1

Generate Candidates + Deduplicate

Try include/exclude recursion across indices, collect every combination that reaches the target, then store normalized combinations inside a set so duplicates collapse.

Problem: This still generates duplicate branches first, especially when repeated values appear in the input. We can prevent duplicates during recursion by sorting and skipping equal values at the same level.

Java — Use a set to deduplicate

 import java.util.*;
class Solution {
public List<List<Integer>> combinationSum2(int[] candidates, int target) {
        Arrays.sort(candidates);
Set<List<Integer>> set = new LinkedHashSet<>();
dfs(candidates, 0, target, new ArrayList<>(), set);
return new ArrayList<>(set);
    }
private void dfs(int[] c, int i, int remain,
List<Integer> path,
Set<List<Integer>> set) {
if (remain == 0) { set.add(new ArrayList<>(path)); return; }
if (i == c.length || remain < 0) return;
        path.add(c[i]);
dfs(c, i + 1, remain - c[i], path, set);
        path.remove(path.size() - 1);
dfs(c, i + 1, remain, path, set);
    }
}

Python — Use a set to deduplicate

 class Solution:
def combinationSum2(self, candidates: list[int], target: int) -> list[list[int]]:
        candidates.sort()
        seen = set()
def dfs(i: int, remain: int, path: list[int]) -> None:
if remain == 0:
                seen.add(tuple(path))
return if i == len(candidates) or remain < 0:
return
path.append(candidates[i])
dfs(i + 1, remain - candidates[i], path)
            path.pop()
dfs(i + 1, remain, path)
dfs(0, target, [])
return [list(t) for t in seen]

Metric	Value
Time	Exponential
Space	Exponential output + set

Section Three · Approach 2

Sorted Backtracking with No Reuse

Sort first. Loop from start. Skip duplicates using i > start && c[i] == c[i-1]. When choosing a number, recurse with i + 1 so the same element index cannot be reused.

💡 Mental model: You are picking coupons from a sorted pile. At one decision level, if two coupons have the same value, starting with the second copy would recreate the same combinations as starting with the first copy. So you skip the later duplicate at that same level. But after taking the first one, taking the second deeper in recursion is fine.

Algorithm

Sort the candidates.
If remain == 0, record the path.
If candidates[i] > remain, break — sorted order lets us prune early.
If i > start && candidates[i] == candidates[i-1], continue — duplicate at same level.
Recurse with i + 1 because each index is used at most once.

🎯 LC 39 vs LC 40: LC 39 reuses the current candidate so it recurses with i. LC 40 forbids reuse, so it recurses with i + 1. That single parameter change is the heart of the problem.

Section Four · Trace

Visual Walkthrough

Trace for sorted [1,1,2,5,6,7,10], target = 8:

Backtracking with same-level duplicate skipping

Section Five · Implementation

Code — Java & Python

Java — Sorted backtracking

 import java.util.*;
class Solution {
public List<List<Integer>> combinationSum2(int[] candidates, int target) {
        Arrays.sort(candidates);
List<List<Integer>> res = new ArrayList<>();
backtrack(candidates, target, 0, new ArrayList<>(), res);
return res;
    }
private void backtrack(int[] c, int remain, int start,
List<Integer> path,
List<List<Integer>> res) {
if (remain == 0) { res.add(new ArrayList<>(path)); return; }
for (int i = start; i < c.length; i++) {
if (i > start && c[i] == c[i - 1]) continue;
if (c[i] > remain) break;
            path.add(c[i]);
backtrack(c, remain - c[i], i + 1, path, res);
            path.remove(path.size() - 1);
        }
    }
}

Python — Sorted backtracking

 class Solution:
def combinationSum2(self, candidates: list[int], target: int) -> list[list[int]]:
        candidates.sort()
        res = []
def backtrack(start: int, remain: int, path: list[int]) -> None:
if remain == 0:
                res.append(path[:])
return for i in range(start, len(candidates)):
if i > start and candidates[i] == candidates[i - 1]:
continue if candidates[i] > remain:
break
path.append(candidates[i])
backtrack(i + 1, remain - candidates[i], path)
                path.pop()
backtrack(0, target, [])
return res

Section Six · Analysis

Complexity Analysis

Approach	Time	Space	Trade-off
Generate + set	Exponential	High	Creates duplicates first
Sorted backtracking ← optimal	Exponential worst-case	O(target) recursion + output	Prunes and avoids duplicate branches

Section Seven · Edge Cases

Edge Cases & Pitfalls

Case	Input	Why It Matters
Duplicate values	`[1,1,1,2], target=3`	Should not duplicate [1,2].
No solution	`[4,5], target=3`	Return empty list.
Single exact match	`[8], target=8`	Return [[8]].
No reuse allowed	`[2], target=4`	Cannot use the same index twice.

⚠ Common Mistake: Reusing the LC 39 recursion and calling with i instead of i + 1. That accidentally allows using the same element multiple times and produces invalid answers.

← Back to Backtracking problems

LearningTree

LC 40 · Combination Sum II — Solution & Explanation | DSA Guide