Skip to content

Volume ITechnology

4.18.2 — Combination Sum ​

LeetCode 39 · Medium · ★ Blind 75

The problem ​

Given distinct positive numbers and a target, return every combination summing to the target. Each number may be used any number of times. Two combinations are different only if the counts differ, so [2,2,3] and [3,2,2] are the same answer and only one should appear.

candidates = [2,3,6,7], target = 7   →  [[2,2,3], [7]]
candidates = [2],       target = 1   →  []

All candidates are at least 2, which matters — see below.

The pattern ​

This is 4.18.1 Subsets's start-index loop with one character changed.

python
backtrack(i + 1, ...)     # subsets: each element used at most once
backtrack(i, ...)         # here:    the same element may be reused

Passing i instead of i + 1 means the loop can pick the same candidate again on the next level. Passing start at all — rather than looping from 0 — is what stops [3,2,2] appearing as well as [2,2,3]: the walk only ever moves forward through the candidate list, so each combination is generated in one fixed order.

Think of this like paying for an exact amount using coins from a cash register that has an infinite supply of each coin type. If you decide to use the "2" coin, you can keep picking the "2" coin again and again (by passing i instead of i + 1). But once you decide you are done using "2" coins and move on to the "3" coin (by advancing the loop), you are never allowed to reach back into the "2" bin again. This strict left-to-right rule prevents you from building both 2+3+2 and 2+2+3.

Those two facts are the whole solution. Everything else is pruning.

The pruning ​

Two conditions end a branch:

  • The running sum equals the target — record it and stop. Adding more can only overshoot, because all candidates are positive.
  • The running sum exceeds the target — abandon it. Same reason.

Both of these depend on all candidates being positive. With negatives allowed, a sum that has overshot could come back down, so neither cut would be safe and the search space would be infinite with reuse permitted. Say this if asked — it is the assumption doing the work.

Sorting the candidates first buys one more cut: once candidates[i] alone exceeds what remains, every later candidate does too, so you can break out of the loop instead of continue. That turns "skip this branch" into "skip all remaining branches".

The solution ​

python
class Solution:
    def combinationSum(self, candidates: List[int], target: int) -> List[List[int]]:
        candidates.sort()                    # (1) enables the break below
        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 candidates[i] > remaining:  # (5)
                    break                    # sorted → everything after is worse

                path.append(candidates[i])  # (6)
                backtrack(i, remaining - candidates[i])    # (7) i, NOT i + 1
                path.pop()  # (8)

        backtrack(0, target)  # (9)
        return result
ts
function combinationSum(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 (candidates[i] > remaining) break;  // (5)

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

  backtrack(0, target);  // (9)
  return result;
}

Line by line ​

(1) Sort the candidates, smallest first. This makes the early stop in line (5) possible. In TypeScript, the comparison (a, b) => a - b is needed, because without it JavaScript sorts numbers as text.

(2) backtrack(start, remaining) builds combinations that use only candidates from position start onward, and still need to add up to remaining.

(3) Nothing remains, so path adds up exactly to the target. Save a copy and stop. Adding more would only overshoot, because every candidate is positive.

(4) Try each candidate from start onward. Never going back to earlier positions is what stops [3, 2, 2] from appearing as well as [2, 2, 3]. Each combination is only ever built in one order, smallest positions first.

(5) This candidate is already too big for what remains. The list is sorted, so every later candidate is at least as big. So break ends the whole loop, not just this one choice.

(6) Take this candidate.

(7) Keep going from the same position i, not i + 1. Staying at i allows the same number to be picked again, which the problem allows. remaining shrinks by the candidate's value.

(8) Undo the take, ready to try the next candidate.

(9) Start from position 0 with the full target.

Counting down with remaining rather than up with a running total. Both work; counting down makes the base case a single comparison against zero and makes the pruning check read naturally.

break, not continue. Because the list is sorted, the first candidate too large for the remaining budget guarantees every later one is too. This is the difference between pruning one branch and pruning all the rest.

backtrack(i, ...). The line that allows reuse. Changing it to i + 1 gives you Combination Sum II's structure — see 4.18.5.

Trace ​

candidates = [2,3,6,7], target = 7.

Start with 2, remaining 5. Take 2 again, remaining 3. Take 2 again, remaining 1 — now every candidate exceeds 1, so break, and this branch dies. Back up: from remaining 3, take 3 → remaining 0 → record [2,2,3] ✓.

Back up further: from remaining 5 take 3 → remaining 2, but start is now at index 1 so 2 is no longer reachable, and 3 > 2 so break. Dead.

Then 6 > 5 at the top level, break. Finally the branch starting at 7 gives remaining 0 → record [7] ✓.

Notice how the start index is what stops [3,2,2] from ever being built.

Complexity ​

Hard to state tightly, and saying so honestly is better than inventing a bound. The usual expression is O(n^{T/m}) where T is the target and m is the smallest candidate — because the deepest a path can go is T/m levels, with up to n branches at each.

For the real answer, say: "the search tree is bounded by depth target / smallest candidate with branching factor n, and the pruning cuts most of it; the output itself can be exponential."

Space is O(T/m) for the recursion depth.

Let's break this down:

  • Time Complexity: At every step in our recursion, we have at most N choices (the number of candidates). The maximum depth of the tree occurs when we repeatedly pick the smallest element m, leading to a maximum depth of T/m. The maximum number of nodes in this tree is loosely bounded by O(N^{T/m}). However, our pruning (candidates[i] > remaining) dramatically shrinks the true number of paths explored.
  • Space Complexity: The maximum depth of the recursion stack is T/m. The path array will also hold at most T/m elements at any time. Thus, the space complexity is O(T/m), excluding the final output array.

Edge cases ​

  • No combination works, like candidates [2] and target 1. The first candidate is already too big, the loop breaks, and the answer is [].
  • The target equals a candidate. That candidate alone is one answer, alongside any longer ones.
  • One candidate that divides the target, like [3] and target 9. The single answer is [3, 3, 3], built by staying at position 0 three times.

Why the candidates must be positive ​

Two things break with a zero or a negative in the list:

  • A zero could be added infinitely often without changing the sum, so the recursion never terminates.
  • A negative means an overshoot can come back, so remaining < 0 is no longer a safe reason to abandon a branch.

The constraint "all candidates ≥ 2" is not decoration. Noticing which constraint makes your pruning legal is a habit worth building — the same reasoning that makes a sliding window valid in 4.6.

Where this goes next ​

  • Combination Sum II — each number used once, and the input has duplicates. Two changes: i + 1, and the sorted duplicate skip. 4.18.5.
  • Combination Sum III — exactly k numbers, drawn from 1 to 9. Add a length check to the base case.
  • Combination Sum IV — despite the name, this is not a backtracking problem. It counts permutations and only asks for the count, so listing them all is far too slow, and the answer is 1-D DP. 4.23. The name misleads on purpose. The clue is that it asks how many rather than which.
  • Coin Change — the fewest coins reaching a target. Same shape, but you want one optimal answer rather than all answers, so it is DP.

The dividing line worth memorising: enumerate when you need every answer; use DP when you need a count or an optimum.

What the interviewer will push on ​

"Why i and not i + 1?" Reuse is allowed.

"Why does the loop start at start rather than 0?" So each combination is generated in one fixed order, which is how duplicates like [3,2,2] are prevented.

"Where is the pruning?" The break on a sorted list, and the remaining == 0 base case.

"What if candidates could be negative or zero?" The pruning becomes invalid and the recursion may not terminate.

"What if you only needed the number of combinations?" Switch to DP — enumerating is wasted work when you never look at the combinations themselves.

One thing to volunteer: say that this is the subsets template with i instead of i + 1. Naming the minimal difference from a problem you already solved is the fastest way to show you have a method.

Next: 4.18.3 Permutations — the third loop shape, where order matters and the start index disappears.

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