Abstract / Summary

Generate all possible combinations of a given size from a set of numbers starting from one up to a specified maximum.

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 75% (1+ million submissions).

Typical patterns to solve this problem:

• 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 generates all possible combinations of k distinct numbers chosen from the range 1 to n. It does so by constructing a binary mask that represents the selection of elements, then iterating through every lexicographic permutation of that mask. For each permutation, the positions of the set bits are translated into the actual numbers of the combination, which are collected into the final result vector.

Initialization

The algorithm begins by creating a vector p that holds n-k zeros followed by k ones. This binary representation encodes the initial combination where the smallest k numbers are selected.

vector<int> p(n-k, 0);
for (int i = 0; i < k; i++)
    p.push_back(1);

The result container is pre-allocated with a reserve of 10000 elements, which reduces the number of dynamic allocations when the number of combinations is moderate.

vector<vector<int>> result;
result.reserve(10000);

An auxiliary vector add is declared to temporarily hold the numbers belonging to the current combination.

Combination Generation

Inside the do-while loop, the algorithm clears the temporary vector add at the start of each iteration. It then scans the mask p and records the indices of all entries equal to 1. Because the mask is zero-based while the required numbers are one-based, each recorded index is incremented by one.

add.clear();
for (int i = 0; i < p.size(); i++)
    if (p[i] == 1)
        add.push_back(i + 1);

The populated add vector now represents one concrete combination, which is appended to the result collection.

result.push_back(add);

Permutation Loop

The core of the enumeration relies on std::next_permutation, which rearranges the mask p into its next lexicographic ordering. The loop continues until all distinct permutations have been visited, guaranteeing that every possible placement of the k ones among the n positions is examined.

} while (next_permutation(p.begin(), p.end()));

Because the initial mask places all zeros before the ones, the first call to next_permutation produces the smallest lexicographic arrangement that contains a 1 at the earliest possible position, and the final arrangement consists of all ones followed by zeros, completing the enumeration.

Result Construction

After the permutation loop terminates, the function returns the fully populated result vector, which contains each combination as a separate inner vector of integers.

return result;

Edge Cases

The algorithm naturally handles the situation where k equals 0. In that case, the mask p consists solely of zeros, the inner loop never pushes any index into add, and a single empty combination is added to result. Conversely, when k equals n, the mask is composed entirely of ones; the inner loop records every index from 1 to n, producing a single combination that contains the full range. The use of next_permutation on a uniformly valued mask (all zeros or all ones) results in a single iteration, correctly reflecting the combinatorial extremes.

Performance Optimizations

Pre-allocating storage for result with reserve(10000) reduces the overhead of repeated memory allocations as combinations are appended. The temporary vector add is reused across iterations; it is cleared rather than re-created, which avoids unnecessary construction and destruction of internal storage. The mask p is a compact representation that leverages the highly optimized next_permutation algorithm from the standard library, providing an efficient means to traverse the combinatorial space without explicit recursion or backtracking. By translating mask positions to actual numbers only after each permutation, the code minimizes work per iteration to a simple linear scan of length n.

Imagine you have a row of special blocks. Some blocks are colored with a zero and some are colored with a one. The number of blocks with a zero is decided by taking n and subtracting k, and the rest of the blocks have a one.

The code starts by putting all these blocks into a long line. It looks at the line to find which positions have a one. If a position has a one, the code remembers the number of that position by adding one to it and puts that number into a small basket. Once it finds all the ones, it places that basket into a bigger toy box that holds all the different combinations.

After finishing one line, the code shuffles the blocks into a brand new order. It uses a clever trick to make sure every single possible way of arranging those zeros and ones is tried exactly once. It keeps doing this over and over again, making new baskets and adding them to the toy box until there are no more ways to rearrange the blocks. When every single arrangement has been checked, the toy box is filled with all the different groups of numbers.

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

Time: exponential
As a rule of thumb, the maximum input size for one second execution time is

• factorial: up to 10 elements
• exponential: up to 20 elements
• polynomial: a few thousand elements
• loglinear: up to 100,000 elements
• linear: a few million elements
• logarithmic: a billion elements
• constant: practically unlimited

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++	Python	Java								TS
	WalkCCC	C++	Python	Java
	leetcode.ca	C++	Python	Java	Rust		C#				Go	TS
	LeetcodeHelp	C++	Python	Java
	MemoryLimitExceeded	C++	Python
	Progiez	C++	Python	Java
github	aylei				Rust
	begeekmyfriend							C
	BigEggStudy						C#
	black-shadows	C++
	chandansgowda		Python
	charles-wangkai			Java
	chenyanzhe	C++
	everthis					JS
	fpdjsns	C++
	gaosq0604		Python
	gouthampradhan			Java
	halfrost										Go
	haoel	C++
	JoshCrozier					JS
	keineahnung2345	C++
	lennylxx	C++
	linouk23	C++
	lkwq007		Python
	luangong	C++
	MacJim	C++
	martianoff								Scala
	qiyuangong		Python
	ruoru				Rust
	suxrobGM						C#
	varunu28			Java
	vli02							C
	vthwang			Java
	wisdompeak	C++
	XiaotaoGuo	C++
	yuanliu666									Kotlin
	zfang399	C++
AlgoMonster	C++, Python, Java, TypeScript
WalkCCC	C++, Python, Java
leetcode.ca	C++, C#, Go, Java, Python, Rust, TypeScript
LeetcodeHelp	C++, Java, Python
MemoryLimitExceeded	Python, C++
Progiez	C++, Java, Python
aylei	Rust
begeekmyfriend	C
BigEggStudy	C#
black-shadows	C++, C++
chandansgowda	Python
charles-wangkai	Java
chenyanzhe	C++
everthis	JavaScript
fpdjsns	C++
gaosq0604	Python
gouthampradhan	Java
halfrost	Go
haoel	C++
JoshCrozier	JavaScript
keineahnung2345	C++
lennylxx	C++
linouk23	C++
lkwq007	Python
luangong	C++
MacJim	C++
martianoff	Scala
qiyuangong	Python
ruoru	Rust
suxrobGM	C#
varunu28	Java
vli02	C
vthwang	Java
wisdompeak	C++
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