Abstract / Summary

Given a set of candidate numbers and a target, find all unique combinations that sum to the target using numbers from the set.

Note

The full problem description, including helpful examples, can be found on LeetCode.

This problem is ranked as

and has an acceptance rate of about 77% (4+ million submissions).

Typical patterns to solve this problem:

• Array
• Backtracking

Every single line of code was written by me, 100% from scratch, between August 2023 and August 2024.
However, two years later I set up this website and used various AI tools to generate most of the walkthrough / explanations below.

See this dedicated page for more details.

Overview

The provided implementation solves the classic “combination sum” problem: given a list of candidate integers (which may contain duplicates) and a target value, it returns all unique combinations where the chosen numbers sum to the target. Each candidate may be used unlimited times. The algorithm builds combinations incrementally using dynamic programming, storing intermediate results keyed by their partial sums. By the end of the process, the set of combinations that achieve the exact target is extracted and returned as a vector of vectors.

Key Steps

Sorting and Initial State

The first operation orders the candidate numbers in non-decreasing order. This ordering is crucial for two reasons: it enables early termination of inner loops when the running sum would exceed the target, and it simplifies duplicate handling by allowing a simple equality check with the previously processed value.

sort(candidates.begin(), candidates.end());
dp[0].insert({{}});

The dynamic-programming table dp is an unordered_map that maps a partial sum to a set of multisets, each multiset representing one combination that yields that sum. The base case inserts an empty multiset for sum zero, establishing the foundation from which larger sums are constructed.

Iterative Construction of Partial Sums

The outer loop iterates over every possible intermediate sum from 0 up to target-1. For each reachable sum i, the algorithm examines every combination (base) that produces i. It computes the actual numeric sum of the elements in base (although i already represents this sum, the explicit calculation is performed to keep the logic independent of the map’s key).

for (int i = 0; i < target; i++) {
    for (const auto& base : dp[i]) {
        auto sum = 0;
        for (auto x : base)
            sum += x;
        // ...
    }
}

Inside this nested loop, a second loop walks through the sorted candidates. The variable prev remembers the last candidate value processed for the current base. If the current candidate equals prev, it is skipped, preventing the generation of duplicate combinations that differ only in the order of identical values.

int prev = -1;
for (auto x : candidates) {
    if (sum + x > target)
        break;
    if (x == prev)
        continue;
    prev = x;
    // ...
}

When a candidate can be added without exceeding the target, a new multiset next is created by copying base and inserting the candidate x. This new combination is then stored in the set associated with the new partial sum sum + x. Because the container type is set<multiset<int>>, duplicate multisets are automatically eliminated, guaranteeing uniqueness of combinations at each sum level.

auto next = base;
next.insert(x);
dp[sum + x].insert(next);

Extraction of Final Combinations

After all partial sums have been processed, the algorithm retrieves the set of multisets stored under the key target. Each multiset is converted into a vector<int> by copying its ordered elements. The resulting vectors are collected into the final result container, which is returned to the caller.

vector<vector<int>> result;
for (auto& base : dp[target])
    result.push_back({base.begin(), base.end()});
return result;

Edge Cases Handled

When the target value is zero, the initial insertion of an empty multiset for sum zero ensures that the algorithm returns a single empty combination, which is the mathematically correct answer. If the candidates vector is empty, the outer loop never finds any base combinations beyond the initial zero sum, and consequently dp[target] remains empty for any positive target, leading to an empty result set. Duplicate values in candidates are filtered out during the inner candidate loop by the prev check, so the algorithm does not produce redundant combinations that differ only by the order of identical numbers. The early break condition if (sum + x > target) break; guarantees that candidates larger than the remaining needed sum are never considered, preventing unnecessary work and avoiding overflow of the target bound.

Performance Optimizations

The use of an unordered_map for dp provides average-case constant-time access to the set of combinations for any given partial sum, which speeds up look-ups compared to a linear search structure. Storing combinations as multiset<int> inside a set automatically enforces both ordering and uniqueness, eliminating the need for explicit duplicate-removal logic after generation. The sorted order of candidates enables the early termination of the inner loop as soon as adding the current candidate would exceed the target, reducing the number of iterations dramatically for large candidate values. Skipping consecutive duplicate candidates with the prev variable prevents the creation of identical multisets, thereby reducing the size of the stored sets and the amount of memory churn caused by redundant insertions. Finally, by building combinations incrementally from smaller sums to larger ones, the algorithm reuses previously computed results instead of recomputing them from scratch, which is a classic dynamic-programming advantage.

Imagine you have a big pile of different colored building blocks, and each block has a secret number written on it. You have a special goal to reach a certain magic number by stacking these blocks together. This code is like building towers to see which groups of blocks add up perfectly to that magic number.

First, the code organizes the blocks by their sizes so it can look at the smallest ones first. It starts with an empty space and begins building. It looks at every goal number from one up to the target number. For every pile of blocks that is already sitting on the table, it tries adding one more block from the pile. If adding a new block makes the tower match the target number exactly, it keeps that combination as a success. If the tower gets too big and goes over the target number, it stops and tries a different block instead. By the time it looks at every possible combination, it has a collection of all the different ways to stack the blocks to reach the exact target, making sure no two towers are the same.

Several LLMs ranked my code quality on a scale from 1 (very poor) to 10 (outstanding):

not analyzed yet

I wrote a basic crawler to find other solutions to that problem.
Obviously, I did that after I solved the problem myself.

In general, AlgoMonster and WalkCCC solutions are high-quality and always worth a look.
I haven't checked most of the other solutions, but they might be helpful as well.

And of course, the LeetCode forum is always a good place (or even the best) to look for alternative approaches.

(click on a column header to sort the table)

	author
author	solutions
www	AlgoMonster	C++	Java	Python										TS
	WalkCCC	C++	Java	Python
	leetcode.ca	C++	Java	Python	C#	Rust						Go	PHP	TS
	LeetcodeHelp	C++	Java	Python
	MemoryLimitExceeded	C++		Python
	Progiez	C++	Java	Python
github	aylei					Rust
	begeekmyfriend							C
	BigEggStudy				C#
	black-shadows	C++
	bujosa			Python
	charles-wangkai		Java
	chenyanzhe	C++
	Dijkstra-Edu		Java
	everthis						JS
	fartem									Ruby
	FelixFan1122				C#
	fengvyi	C++
	fpdjsns	C++
	gaosq0604			Python
	Garvit244			Python
	gouthampradhan		Java
	halfrost											Go
	haoel	C++
	JoshCrozier						JS
	keineahnung2345	C++
	lennylxx	C++
	linouk23	C++
	lkwq007			Python
	luangong	C++
	MacJim	C++
	martianoff								Scala
	qiyuangong		Java
	ruoru					Rust
	shreymehul				C#
	sonugiri1043	C++
	suxrobGM				C#
	trung-hn			Python
	varunu28		Java
	vli02							C
	vthwang		Java
	XiaotaoGuo	C++
	yuanliu666										Kotlin
	zfang399	C++
AlgoMonster	C++, Python, Java, TypeScript
WalkCCC	C++, Python, Java
leetcode.ca	C++, C#, Go, Java, PHP, Python, Rust, TypeScript
LeetcodeHelp	C++, Java, Python
MemoryLimitExceeded	Python, C++
Progiez	C++, Java, Python
aylei	Rust
begeekmyfriend	C
BigEggStudy	C#
black-shadows	C++, C++
bujosa	Python
charles-wangkai	Java
chenyanzhe	C++
Dijkstra-Edu	Java
everthis	JavaScript
fartem	Ruby
FelixFan1122	C#
fengvyi	C++
fpdjsns	C++
gaosq0604	Python
Garvit244	Python
gouthampradhan	Java
halfrost	Go
haoel	C++
JoshCrozier	JavaScript
keineahnung2345	C++
lennylxx	C++
linouk23	C++
lkwq007	Python
luangong	C++
MacJim	C++
martianoff	Scala
qiyuangong	Java
ruoru	Rust
shreymehul	C#
sonugiri1043	C++
suxrobGM	C#
trung-hn	Python
varunu28	Java
vli02	C
vthwang	Java
XiaotaoGuo	C++
yuanliu666	Kotlin
zfang399	C++

There are a few extra pages giving you some insights into my setup:

• Tech Stack - my development environment and tools
• AI - how AI helped me create this website (NOT solving the problems)
• Progress - progression over time
• Quality - code quality