Skip to content

Volume ITechnology

4.18.5 — Combination Sum II ​

LeetCode 40 · Medium

The problem ​

Find every unique combination summing to the target. Each number in the input may be used at most once, and the input may contain duplicates.

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

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

[1,1,6] uses both 1s, which is legal because there are two of them. But [1,7] appears only once, even though either 1 could have formed it.

The pattern ​

This is 4.18.2 Combination Sum and 4.18.4 Subsets II combined, with two changes from Combination Sum:

changereason
backtrack(i + 1, ...) instead of ieach element used at most once
the sorted duplicate skipthe input has repeats

Neither is new. What makes this problem worth doing is that the two rules look like they contradict each other and do not.

Think of this like selecting team members from a fixed pool of applicants, where two applicants might happen to be identical twins with the exact same skills (say, two "1"s). If you need two "1"s on your team, you can absolutely hire both twins (backtrack(i + 1) lets you pick the next available person). But if you only need one "1", you shouldn't create "Team A with Twin 1" and then later create a separate "Team B with Twin 2" because the resulting teams would be functionally identical. The duplicate skip prevents hiring the second twin instead of the first.

The rule that looks contradictory ​

[1,1,6] is a valid answer. So two 1s can appear in the same combination. But the duplicate skip says do not use the same value twice.

Both are true, because they are talking about different things:

  • Two 1s in the same combination is a value used at two different depths of the tree — one 1 is the parent choice, the other is a child choice. Allowed, and that is what i + 1 supports: the second 1 is a different array element.
  • Two 1s as different first choices is a value tried twice among siblings — same depth, same position. That produces the identical subtree twice. Forbidden.

The guard i > start separates them precisely, because i == start is the first choice at this level, which may legitimately equal the parent's value.

This is the same reasoning as 4.18.4, and if it did not fully land there, this problem is where it should.

The solution ​

python
class Solution:
    def combinationSum2(self, candidates: List[int], target: int) -> List[List[int]]:
        candidates.sort()  # (1)
        result = []
        path = []

        def backtrack(start: int, remaining: int):  # (2)
            if remaining == 0:  # (3)
                result.append(path[:])
                return

            for i in range(start, len(candidates)):  # (4)
                if i > start and candidates[i] == candidates[i - 1]:  # (5)
                    continue                          # sibling duplicate
                if candidates[i] > remaining:  # (6)
                    break                             # sorted → all later ones too big

                path.append(candidates[i])  # (7)
                backtrack(i + 1, remaining - candidates[i])   # (8) i + 1: no reuse
                path.pop()  # (9)

        backtrack(0, target)
        return result
ts
function combinationSum2(candidates: number[], target: number): number[][] {
  candidates.sort((a, b) => a - b);  // (1)
  const result: number[][] = [];
  const path: number[] = [];

  function backtrack(start: number, remaining: number): void {  // (2)
    if (remaining === 0) {  // (3)
      result.push([...path]);
      return;
    }
    for (let i = start; i < candidates.length; i++) {  // (4)
      if (i > start && candidates[i] === candidates[i - 1]) continue;  // (5)
      if (candidates[i] > remaining) break;  // (6)

      path.push(candidates[i]);  // (7)
      backtrack(i + 1, remaining - candidates[i]);  // (8)
      path.pop();  // (9)
    }
  }

  backtrack(0, target);
  return result;
}

Line by line ​

(1) Sort the candidates. Equal values become neighbours, and the early stop in line (6) becomes safe.

(2) backtrack(start, remaining) builds combinations from positions start onward that must still add up to remaining.

(3) Nothing remains, so path adds up to the target exactly. Save a copy.

(4) Try each candidate from start onward as the next number.

(5) Skip a value a sibling already tried. This is the guard from 4.18.4 Subsets II. If this value equals the one before it, and both were options in this same loop, then using it again would build the same combinations twice.

(6) Too big for what remains. Every later candidate is at least as big, so stop the whole loop.

(7) Take this candidate,

(8) continue from the next position, i + 1, because each candidate may be used only once, and

(9) undo.

The sort does two jobs. It makes equal values adjacent so the duplicate guard works, and it makes the break legal so one oversized candidate prunes all the rest.

Order of the two checks. The duplicate skip uses continue and must come before the break, because a skipped duplicate is not a reason to abandon the whole loop.

remaining == 0 is the only success case. Since all candidates are positive, overshooting is caught by the break and never reaches the base case as a negative.

Trace ​

[10,1,2,7,6,1,5] sorted is [1,1,2,5,6,7,10], target 8.

At start = 0, i = 0 (the first 1): allowed. Path [1], remaining 7, recurse from index 1.

  • i = 1 (the second 1): i == start here (start is 1), so allowed. Path [1,1], remaining 6 → eventually reaches 6 and records [1,1,6] ✓.
  • i = 2 (value 2): path [1,2], remaining 5 → picks up 5 → [1,2,5] ✓.
  • i = 3 (value 5): remaining 2, and everything from here is larger → dead.
  • i = 5 (value 7): remaining 0 → [1,7] ✓.

Back at start = 0, i = 1 (the second 1): now i > start and it equals candidates[0] → skipped. That is what prevents a second [1,7] and a second [1,2,5].

Then i = 2 (value 2): path [2], remaining 6 → [2,6] ✓.

Four unique combinations. ✓

Complexity ​

Bounded by O(2^n \times n) in the worst case — the number of subsets — though the sum constraint and the two prunings cut it far below that in practice.

O(n) space beyond the output.

Let's break this down:

  • Time Complexity: Sorting takes O(n \log n). In the worst case (e.g., all 1s and a large target), the number of valid combinations can be exponential. Our recursive tree has a maximum depth of n (since no reuse is allowed). Bounded loosely by O(2^n), but heavily pruned by both the duplicate skip and early termination (break). Creating the copies takes O(k) per valid path.
  • Space Complexity: The maximum recursion depth is n. The path list stores at most n items. Therefore, the auxiliary space is O(n).

Edge cases ​

  • Repeated candidates, like [1, 1, 2] with target 3. [1, 2] appears once, not twice, thanks to line (5). [1, 1] can still be built, because the second 1 is a child of the first, not a sibling.
  • No combination works. The answer is [].

The comparison worth memorising ​

problemreuseduplicates in inputrecurse withduplicate guard
Subsetsnonoi + 1none
Subsets IInoyesi + 1i > start
Combination Sumyesnoinone
Combination Sum IInoyesi + 1i > start

Four problems, two independent switches. Once you see the table, they stop being four problems.

Where this goes next ​

  • Palindrome Partitioning — the same start-index loop where the choice is where to cut rather than which element to take. 4.18.7.
  • Combination Sum III — exactly k numbers from 1 to 9, so add a length check.
  • Partition to K Equal Sum Subsets — much harder, and it needs both this template and memoisation over a bitmask of used elements.

What the interviewer will push on ​

"How can [1,1,6] be valid if you skip duplicates?" Depth versus siblings. This is the question the problem exists to ask, so have the sentence ready.

"Why i + 1 here but i in Combination Sum?" Reuse allowed or not.

"Why sort?" Two reasons: the duplicate guard needs adjacency, and the break needs order.

"Why continue for one check and break for the other?" A duplicate skips one branch; an oversized candidate kills every remaining branch.

One thing to volunteer: put the four-problem table on the whiteboard. It shows that you see a family with two switches rather than four separate memorised solutions, and that is exactly the transferable understanding being tested.

Next: 4.18.6 Word Search — backtracking on a grid, where the state being undone is the board itself.

Combine chapters into one PDF

Pick the chapters you want. They print in the order you pick them.

Volume I — Technology
Part 0 — Retention & Notation
Part 1 — Foundations of Computation
Part 2 — Operating Systems
2.1 The Kernel
2.2 Processes
2.3 Threads & Scheduling
2.4 Concurrency Under the Hood
2.5 Memory Management
2.6 File Systems
2.7 Input/Output
2.8 Linux for Engineers
2.9 Windows & macOS in Practice
Part 3 — Languages, Compilers & Runtimes
3.6 JavaScript & V8
3.7 TypeScript
3.8 Node.js Internals
3.13 Python & CPython
3.14 FastAPI & Production Python
Part 4 — Data Structures & Algorithms
4.0 Classic Problems — Before NeetCode
4.4 Arrays & Hashing — Problems
4.5 Two Pointers
4.6 Sliding Window
4.8 Stack — Problems
4.9 Linked List — Problems
4.11 Binary Search — Problems
4.13 Trees
4.14 Tree — Problems
4.15 Trie — Problems
4.17 Heap — Problems
4.18 Backtracking — Problems
4.19 Graphs
4.20 Graph — Problems
4.21 Advanced Graph — Problems
4.23 1-D DP — Problems
4.24 2-D DP — Problems
4.26 Greedy — Problems
4.27 Interval — Problems
4.28 Math & Geometry — Problems
4.30 Bit Manipulation — Problems
Part 5 — Networking & the Web
5.3 IP
5.4 Transport
5.6 HTTP
Part 6 — Frontend Engineering
6.1 Browser Internals
6.2 HTML & CSS Mastery
6.3 JavaScript in the Browser
6.4 React, from First Component to Full Shop
6.5 Frameworks & Rendering
6.8 UI Engineering & Patterns
Part 7 — Databases & Storage
7.2 SQL Mastery
7.3 Storage Engine Internals
7.4 Transactions
7.5 NoSQL Taxonomy
7.8 Analytics & Big Data
Part 8 — Security, Identity & Cryptography
8.2 Cryptography
8.3 Protocols of Trust
8.4 Identity: AuthN & AuthZ
8.5 Application Security
8.6 Infrastructure Security
Part 9 — Software Design (LLD)
9.2 OOP Foundations
9.3 Design Principles
9.4 Design Patterns
9.5 Concurrency
9.6 API Design
9.7 LLD Interview Machines
9.9 Node/Express Production Playbook
Part 10 — Distributed Systems & HLD
10.7 Consistency & Consensus
10.8 Messaging & Microservices
10.14 Caching
Building blocks from the design seat
Part 11 — System Design Case Studies
Part 12 — AI & ML Engineering
12.1 What AI Engineering Is
12.2 The Math You Need
12.3 Classical Machine Learning
12.4 Data for ML
12.5 Deep Learning
12.6 Embeddings & Vector Search
12.7 Transformers & LLMs
12.8 Building with LLMs
12.9 Retrieval-Augmented Generation
12.10 Agents
12.11 Adapting Models
12.12 Production AI
12.13 Multimodal AI
12.14 AI Security & Governance
12.15 Case Studies & Capstone
Part 13 — Cloud, DevOps & Infrastructure
13.11 Git, from First Commit to Team Workflow
Part 14 — Containers: Docker & Kubernetes
14.1 Foundations
14.2 Docker
14.3 Kubernetes
14.4 Kubernetes on Azure
Part 15 — The Craft & Career
Nothing picked yet