Combinations (LeetCode
Learn how to solve the Combinations problem using backtracking, pruning, iterative construction, and lexicographic generation. Includes intuition, recursion trees, Java code, dry runs, complexity analysis, interview tips, and production applications.
Introduction
Combinations is a foundational backtracking problem that teaches how to select a fixed number of elements without considering their order.
It is frequently discussed in interviews at companies such as:
- Amazon
- Microsoft
- Meta
- Apple
- Adobe
- Bloomberg
- Goldman Sachs
- JPMorgan Chase
This problem evaluates your understanding of:
- Backtracking
- Combination generation
- Start-index management
- State restoration
- Search-space pruning
- Binomial coefficients
- Output-sensitive complexity
The main idea is:
Build a selection from left to right, always choosing the next value from the remaining range.
This prevents duplicate arrangements such as:
[1,2]
and:
[2,1]
from being generated separately.
Problem Statement
Given two integers, n and k, return all possible combinations of k numbers chosen from the range:
1 to n
The combinations may be returned in any order.
Example 1
Input
n = 4
k = 2
Output
[
[1,2],
[1,3],
[1,4],
[2,3],
[2,4],
[3,4]
]
Example 2
Input
n = 1
k = 1
Output
[
[1]
]
What Is a Combination?
A combination is a selection of elements where order does not matter.
For:
[1,2,3]
combinations of size 2 are:
[1,2]
[1,3]
[2,3]
The following are not treated as separate combinations:
[2,1]
[3,1]
[3,2]
They contain the same selected values in a different order.
Combination vs Permutation
| Combination | Permutation |
|---|---|
| Order does not matter | Order matters |
[1,2] equals [2,1] |
[1,2] differs from [2,1] |
| Uses a forward start index | Tries every unused element |
Count is C(n,k) |
Count is P(n,k) |
For:
n = 4
k = 2
Number of combinations:
C(4,2) = 6
Number of permutations of length 2:
P(4,2) = 12
How Many Combinations Exist?
The number of ways to choose k elements from n elements is:
C(n,k)
=
n!
────────────
k!(n-k)!
Example:
graph TD
C_0_0["C"] --> N_4_1_1["4"]
N_4_1_1["4"] --> N_2_2_1["2"]
N_4_1_1["4"] --> N_2_2_2["2"]
N_2_2_1["2"] --> N_24_3_1["24"]
N_2_2_1["2"] --> N_4_3_2["4"]
N_24_3_1["24"] --> N_6_4_1["6"]
Combination Decision Tree
For:
n = 4
k = 2
Start with:
[]
The first selected value can be:
1, 2, or 3
There is no need to begin with 4 because no value remains to complete a size-2 combination.
graph TD
N_1_0_0["1"] --> N_1_1_1["1"]
N_1_0_0["1"] --> N_2_1_2["2"]
N_2_0_1["2"] --> N_1_1_3["1"]
N_2_0_1["2"] --> N_3_1_4["3"]
N_3_0_2["3"] --> N_1_1_5["1"]
N_3_0_2["3"] --> N_4_1_6["4"]
Every leaf at depth k is a complete combination.
Backtracking State
The recursive state contains:
start— next available numbercurrent— combination being constructedresult— completed combinations
At each recursion level:
- Try every number from
startton. - Add the number to the current combination.
- Recurse using the next number.
- Remove the number to restore state.
Backtracking Template
void backtrack(
int start,
List<Integer> current) {
if (current.size() == k) {
saveResult();
return;
}
for (int number = start;
number <= n;
number++) {
current.add(number);
backtrack(
number + 1,
current);
current.remove(
current.size() - 1);
}
}
Approach 1 — Standard Backtracking
Core Idea
Always move forward after selecting a number.
If the current selection includes:
2
the next choice starts at:
3
This guarantees:
- No element is reused.
- Combinations stay in increasing order.
- Duplicate arrangements are avoided.
Java Code — Standard Backtracking
import java.util.ArrayList;
import java.util.List;
public class Combinations {
public List<List<Integer>> combine(
int n,
int k) {
if (n < 0 || k < 0 || k > n) {
throw new IllegalArgumentException(
"Require 0 <= k <= n");
}
List<List<Integer>> result =
new ArrayList<>();
backtrack(
1,
n,
k,
new ArrayList<>(),
result);
return result;
}
private void backtrack(
int start,
int n,
int k,
List<Integer> current,
List<List<Integer>> result) {
if (current.size() == k) {
result.add(
new ArrayList<>(current));
return;
}
for (int number = start;
number <= n;
number++) {
current.add(number);
backtrack(
number + 1,
n,
k,
current,
result);
current.remove(
current.size() - 1);
}
}
}
Choose–Explore–Unchoose
Choose
current.add(number);
The number becomes part of the current combination.
Explore
backtrack(
number + 1,
n,
k,
current,
result);
Only larger numbers are available in the next recursive call.
Unchoose
current.remove(
current.size() - 1);
Restore the previous state before trying the next candidate.
Why Recurse with number + 1?
Suppose the current number is:
2
The next recursive call begins at:
3
This prevents:
- Reusing
2 - Generating
[2,1] - Revisiting earlier choices
- Creating duplicate combinations
Using:
start + 1
would be incorrect inside the loop because the recursive start must depend on the number actually selected.
Detailed Dry Run
Input:
n = 4
k = 2
Initial state:
start = 1
current = []
Choose 1
current = [1]
Recurse with:
start = 2
Choose 2
current = [1,2]
Size equals k.
Save:
[1,2]
Backtrack:
current = [1]
Choose 3
current = [1,3]
Save:
[1,3]
Backtrack.
Choose 4
current = [1,4]
Save:
[1,4]
Backtrack completely:
current = []
Choose 2
current = [2]
Recurse from:
3
Generate:
[2,3]
[2,4]
Choose 3
current = [3]
Recurse from:
4
Generate:
[3,4]
Choose 4
current = [4]
No larger number remains.
This branch cannot reach size 2, so it returns without producing a result.
The optimized solution will prune this branch before entering it.
Final Result
[
[1,2],
[1,3],
[1,4],
[2,3],
[2,4],
[3,4]
]
Dry Run Table
| Start | Current Before | Choice | Current After | Action |
|---|---|---|---|---|
| 1 | [] |
1 | [1] |
Recurse |
| 2 | [1] |
2 | [1,2] |
Save |
| 2 | [1] |
3 | [1,3] |
Save |
| 2 | [1] |
4 | [1,4] |
Save |
| 1 | [] |
2 | [2] |
Recurse |
| 3 | [2] |
3 | [2,3] |
Save |
| 3 | [2] |
4 | [2,4] |
Save |
| 1 | [] |
3 | [3] |
Recurse |
| 4 | [3] |
4 | [3,4] |
Save |
Why Copy the Current List?
Correct:
result.add(
new ArrayList<>(current));
Incorrect:
result.add(current);
The current list is mutable and reused by every recursive branch.
Without copying, later backtracking operations would modify previously stored results.
Approach 2 — Backtracking with Pruning
Core Idea
Do not start a branch when too few numbers remain to complete a size-k combination.
Suppose:
n = 5
k = 3
current.size() = 1
We still need:
3 - 1 = 2
numbers.
If the current candidate is 5, no values remain after it, so the branch cannot succeed.
Calculate How Many Values Are Still Needed
int needed =
k - current.size();
If choosing number still requires needed - 1 later values, the largest valid starting candidate is:
n - needed + 1
Therefore, the optimized loop becomes:
for (int number = start;
number <= n - needed + 1;
number++)
Pruning Example
For:
n = 4
k = 2
current = []
Needed:
2
Largest first choice:
4 - 2 + 1 = 3
So the root loop tries only:
1, 2, 3
It does not try 4, because no number remains to form a pair.
Java Code — Optimized Backtracking
import java.util.ArrayList;
import java.util.List;
public class CombinationsOptimized {
public List<List<Integer>> combine(
int n,
int k) {
if (n < 0 || k < 0 || k > n) {
throw new IllegalArgumentException(
"Require 0 <= k <= n");
}
List<List<Integer>> result =
new ArrayList<>();
backtrack(
1,
n,
k,
new ArrayList<>(),
result);
return result;
}
private void backtrack(
int start,
int n,
int k,
List<Integer> current,
List<List<Integer>> result) {
if (current.size() == k) {
result.add(
new ArrayList<>(current));
return;
}
int needed =
k - current.size();
int maximumCandidate =
n - needed + 1;
for (int number = start;
number <= maximumCandidate;
number++) {
current.add(number);
backtrack(
number + 1,
n,
k,
current,
result);
current.remove(
current.size() - 1);
}
}
}
Why the Pruning Formula Works
Suppose the current candidate is number.
The number of available values from number through n is:
n - number + 1
To complete the combination, we need:
needed
values including the current candidate.
Therefore:
n - number + 1 >= needed
Rearranging:
number <= n - needed + 1
This gives the optimized upper boundary.
Alternative Pruning Condition
The same idea can be written inside the loop:
for (int number = start;
number <= n;
number++) {
int remainingValues =
n - number + 1;
int needed =
k - current.size();
if (remainingValues < needed) {
break;
}
// Choose and recurse
}
The precomputed loop boundary is cleaner.
Complexity Analysis
There are:
C(n,k)
completed combinations.
Each result contains:
k
values and requires O(k) time to copy.
Therefore, the output-sensitive time complexity is:
O(k × C(n,k))
The recursion stack and current path require:
O(k)
auxiliary space.
Complexity Summary
| Complexity | Value |
|---|---|
| Time | O(k × C(n,k)) |
| Output Space | O(k × C(n,k)) |
| Auxiliary Space | O(k) |
| Maximum Recursion Depth | O(k) |
The algorithm also visits partial states, but the dominant cost is producing and copying the complete output.
Why Is the Complexity Not O(2^n)?
A subset problem may generate selections of every possible size, resulting in:
2^n
outputs.
The Combinations problem generates only selections of exactly size k.
The number of outputs is:
C(n,k)
For some values of k, especially near n / 2, this is still very large.
Special Combination Cases
k = 0
Mathematically:
C(n,0) = 1
There is one valid combination:
[]
The implementation returns:
[[]]
because the base condition is true during the initial call.
k = n
There is exactly one combination:
[1,2,3,...,n]
k = 1
Every number forms its own combination.
For:
n = 4
result:
[
[1],
[2],
[3],
[4]
]
k > n
No valid combination exists.
A coding platform may return an empty result.
Production code may reject the input as invalid.
Approach 3 — Include or Exclude Recursion
Core Idea
At every number, choose between:
- Including the number
- Excluding the number
This is similar to the Subsets problem, except only selections of size k are saved.
Java Code — Include or Exclude
import java.util.ArrayList;
import java.util.List;
public class CombinationsIncludeExclude {
public List<List<Integer>> combine(
int n,
int k) {
List<List<Integer>> result =
new ArrayList<>();
backtrack(
1,
n,
k,
new ArrayList<>(),
result);
return result;
}
private void backtrack(
int number,
int n,
int k,
List<Integer> current,
List<List<Integer>> result) {
if (current.size() == k) {
result.add(
new ArrayList<>(current));
return;
}
if (number > n) {
return;
}
current.add(number);
backtrack(
number + 1,
n,
k,
current,
result);
current.remove(
current.size() - 1);
backtrack(
number + 1,
n,
k,
current,
result);
}
}
Include or Exclude Pruning
If the number of remaining values is smaller than the number still needed, stop the branch.
int remaining =
n - number + 1;
int needed =
k - current.size();
if (remaining < needed) {
return;
}
Optimized Include or Exclude Code
private void backtrack(
int number,
int n,
int k,
List<Integer> current,
List<List<Integer>> result) {
if (current.size() == k) {
result.add(
new ArrayList<>(current));
return;
}
if (number > n) {
return;
}
int remaining =
n - number + 1;
int needed =
k - current.size();
if (remaining < needed) {
return;
}
current.add(number);
backtrack(
number + 1,
n,
k,
current,
result);
current.remove(
current.size() - 1);
backtrack(
number + 1,
n,
k,
current,
result);
}
The for-loop backtracking solution is generally shorter and preferred in interviews.
Approach 4 — Iterative Combination Construction
Core Idea
Build combinations one number at a time.
Start with:
[[]]
For each number:
- Copy existing combinations whose size is less than
k. - Add the number.
- Store only combinations up to size
k.
A cleaner iterative approach maintains lists grouped by size.
Java Code — Iterative Dynamic Construction
import java.util.ArrayList;
import java.util.List;
public class CombinationsIterative {
public List<List<Integer>> combine(
int n,
int k) {
List<List<List<Integer>>> bySize =
new ArrayList<>();
for (int size = 0;
size <= k;
size++) {
bySize.add(
new ArrayList<>());
}
bySize.get(0)
.add(
new ArrayList<>());
for (int number = 1;
number <= n;
number++) {
int largestSize =
Math.min(
number,
k);
for (int size = largestSize;
size >= 1;
size--) {
List<List<Integer>> previous =
bySize.get(size - 1);
List<List<Integer>> additions =
new ArrayList<>();
for (List<Integer> combination
: previous) {
List<Integer> candidate =
new ArrayList<>(
combination);
candidate.add(number);
additions.add(candidate);
}
bySize.get(size)
.addAll(additions);
}
}
return bySize.get(k);
}
}
Why Iterate Sizes Backward?
When processing one number, it must be used at most once.
If sizes are updated from small to large, newly created combinations might be reused immediately and include the same number multiple times.
Iterating backward prevents this.
Approach 5 — Lexicographic Generation
Core Idea
Combinations can be generated in sorted lexicographic order without recursion.
Represent a combination using an integer array:
[1,2,...,k]
Repeatedly find the rightmost position that can be incremented.
Example
For:
n = 5
k = 3
Sequence:
[1,2,3]
[1,2,4]
[1,2,5]
[1,3,4]
[1,3,5]
[1,4,5]
[2,3,4]
[2,3,5]
[2,4,5]
[3,4,5]
Java Code — Lexicographic Combinations
import java.util.ArrayList;
import java.util.List;
public class LexicographicCombinations {
public List<List<Integer>> combine(
int n,
int k) {
List<List<Integer>> result =
new ArrayList<>();
if (k < 0 || k > n) {
return result;
}
if (k == 0) {
result.add(
new ArrayList<>());
return result;
}
int[] combination =
new int[k];
for (int i = 0; i < k; i++) {
combination[i] = i + 1;
}
while (true) {
result.add(
toList(combination));
int position =
k - 1;
while (position >= 0
&& combination[position]
== n - k + position + 1) {
position--;
}
if (position < 0) {
break;
}
combination[position]++;
for (int i = position + 1;
i < k;
i++) {
combination[i] =
combination[i - 1] + 1;
}
}
return result;
}
private List<Integer> toList(
int[] combination) {
List<Integer> result =
new ArrayList<>(
combination.length);
for (int value : combination) {
result.add(value);
}
return result;
}
}
Backtracking vs Lexicographic Generation
| Backtracking | Lexicographic |
|---|---|
| Recursive | Iterative |
| Easy to add constraints | Best for generating all in order |
| Natural pruning | Harder to customize |
| Uses current path | Uses fixed-size index array |
| Preferred for interviews | Useful advanced alternative |
Generate Combinations from an Array
The original problem selects values from:
1 to n
A common variation selects k values from an arbitrary array.
Java Code — Array Combinations
import java.util.ArrayList;
import java.util.List;
public class ArrayCombinations {
public List<List<Integer>> combine(
int[] nums,
int k) {
if (k < 0 || k > nums.length) {
throw new IllegalArgumentException(
"Invalid combination size");
}
List<List<Integer>> result =
new ArrayList<>();
backtrack(
nums,
0,
k,
new ArrayList<>(),
result);
return result;
}
private void backtrack(
int[] nums,
int start,
int k,
List<Integer> current,
List<List<Integer>> result) {
if (current.size() == k) {
result.add(
new ArrayList<>(current));
return;
}
int needed =
k - current.size();
int maximumIndex =
nums.length - needed;
for (int i = start;
i <= maximumIndex;
i++) {
current.add(nums[i]);
backtrack(
nums,
i + 1,
k,
current,
result);
current.remove(
current.size() - 1);
}
}
}
Handling Duplicate Input Values
Suppose:
nums = [1,2,2,3]
k = 2
Without duplicate handling, the algorithm may generate:
[1,2]
more than once.
Duplicate Handling Strategy
- Sort the input.
- Skip equal values at the same recursion level.
Condition:
if (i > start
&& nums[i] == nums[i - 1]) {
continue;
}
Java Code — Unique Combinations
import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;
public class UniqueArrayCombinations {
public List<List<Integer>> combineUnique(
int[] nums,
int k) {
Arrays.sort(nums);
List<List<Integer>> result =
new ArrayList<>();
backtrack(
nums,
0,
k,
new ArrayList<>(),
result);
return result;
}
private void backtrack(
int[] nums,
int start,
int k,
List<Integer> current,
List<List<Integer>> result) {
if (current.size() == k) {
result.add(
new ArrayList<>(current));
return;
}
int needed =
k - current.size();
int maximumIndex =
nums.length - needed;
for (int i = start;
i <= maximumIndex;
i++) {
if (i > start
&& nums[i]
== nums[i - 1]) {
continue;
}
current.add(nums[i]);
backtrack(
nums,
i + 1,
k,
current,
result);
current.remove(
current.size() - 1);
}
}
}
Why Skip Duplicates Only at the Same Level?
For:
[1,2,2]
both 2 values may appear in:
[2,2]
Therefore, duplicate values cannot be skipped globally.
The condition:
i > start
means the equal value is skipped only when another equal value has already been considered as an alternative at the same recursion depth.
Common Interview Mistakes
Mistake 1 — Treating Combinations Like Permutations
Incorrectly looping from 0 at every level generates reordered duplicates.
For combinations, always move forward using a start index.
Mistake 2 — Recursing with start + 1
Correct:
backtrack(number + 1, ...);
or for arrays:
backtrack(i + 1, ...);
The next start depends on the actual selected candidate.
Mistake 3 — Forgetting to Copy the Current List
Correct:
result.add(
new ArrayList<>(current));
Mistake 4 — Forgetting to Remove the Last Choice
After recursion:
current.remove(
current.size() - 1);
This restores state for sibling branches.
Mistake 5 — Saving Partial Combinations
Save only when:
current.size() == k
Mistake 6 — Missing Pruning Opportunities
Branches that cannot collect enough remaining values should not be explored.
Use:
n - needed + 1
as the maximum candidate.
Mistake 7 — Incorrect Complexity
The output count is:
C(n,k)
Copying each size-k result costs:
O(k)
Therefore:
O(k × C(n,k))
Mistake 8 — Using a Set to Remove Duplicate Results
For duplicate inputs, sort and prune duplicate branches rather than generating duplicates and removing them afterward.
Production Applications
Combination generation appears in:
- Team selection
- Product bundling
- Feature selection
- Portfolio construction
- Test-case generation
- Permission grouping
- Resource allocation
- Committee selection
- Promotion package generation
- Experiment configuration
Real-World Example — Team Selection
Suppose a manager must select two engineers from four:
Alice
Bob
Carol
David
Possible teams:
[Alice, Bob]
[Alice, Carol]
[Alice, David]
[Bob, Carol]
[Bob, David]
[Carol, David]
The order of team members does not matter.
This is a combination problem.
Real-World Example — Product Bundles
Suppose a store offers four products and wants every two-product bundle.
The combinations are generated without treating:
Laptop + Mouse
and:
Mouse + Laptop
as different bundles.
Constraints such as incompatible products can be used to prune branches.
Constrained Combinations
Backtracking becomes more useful when not every selection is valid.
Possible constraints include:
- Total cost must stay under a budget.
- Members must come from different departments.
- At least one required category must be present.
- Some values cannot appear together.
- The selected values must reach a target sum.
Example — Budget-Constrained Selection
Track the running cost.
if (currentCost > budget) {
return;
}
When all costs are non-negative, exceeding the budget allows immediate pruning.
This idea leads toward the Combination Sum problem.
Generate Only One Valid Combination
Some problems ask whether at least one valid selection exists.
Return a boolean and stop when a solution is found.
private boolean backtrack(...) {
if (current.size() == k) {
return isValid(current);
}
for (...) {
choose();
if (backtrack(...)) {
return true;
}
unchoose();
}
return false;
}
Lazy Combination Processing
Storing all combinations may consume large memory.
Instead, process each completed combination through a callback.
Java Code — Lazy Combination Processor
import java.util.ArrayList;
import java.util.List;
import java.util.function.Consumer;
public class LazyCombinationProcessor {
public void generate(
int n,
int k,
Consumer<List<Integer>> consumer) {
backtrack(
1,
n,
k,
new ArrayList<>(),
consumer);
}
private void backtrack(
int start,
int n,
int k,
List<Integer> current,
Consumer<List<Integer>> consumer) {
if (current.size() == k) {
consumer.accept(
List.copyOf(current));
return;
}
int needed =
k - current.size();
int maximumCandidate =
n - needed + 1;
for (int number = start;
number <= maximumCandidate;
number++) {
current.add(number);
backtrack(
number + 1,
n,
k,
current,
consumer);
current.remove(
current.size() - 1);
}
}
}
This reduces retained output memory but does not change the number of combinations that must be processed.
Count Combinations Without Generating Them
If only the count is needed, calculate:
C(n,k)
directly.
Avoid factorials because they overflow quickly.
Java Code — Safe Binomial Coefficient
public class CombinationCount {
public long count(
int n,
int k) {
if (n < 0 || k < 0 || k > n) {
return 0L;
}
k = Math.min(
k,
n - k);
long result = 1L;
for (int i = 1;
i <= k;
i++) {
result =
result
* (n - k + i)
/ i;
}
return result;
}
}
This uses the identity:
C(n,k) = C(n,n-k)
to minimize iterations.
For very large inputs, use BigInteger.
Java Code — BigInteger Combination Count
import java.math.BigInteger;
public class LargeCombinationCount {
public BigInteger count(
int n,
int k) {
if (n < 0 || k < 0 || k > n) {
return BigInteger.ZERO;
}
k = Math.min(
k,
n - k);
BigInteger result =
BigInteger.ONE;
for (int i = 1;
i <= k;
i++) {
result = result.multiply(
BigInteger.valueOf(
n - k + i));
result = result.divide(
BigInteger.valueOf(i));
}
return result;
}
}
Parallelizing Combination Generation
Top-level branches are independent.
For example, combinations beginning with:
1
can be generated separately from combinations beginning with:
2
However:
- Each branch must use independent mutable state.
- Result merging adds overhead.
- The output may already be very large.
- Small inputs do not justify parallel execution.
- Recursive parallelism can overload thread pools.
Parallel generation is useful only for large, expensive, constrained searches.
Backtracking vs Dynamic Programming
| Backtracking | Dynamic Programming |
|---|---|
| Generates actual combinations | Often counts combinations |
| Supports custom constraints | Reuses overlapping states |
| Output may be exponential | Can avoid materializing outputs |
| Uses choose–explore–unchoose | Uses recurrence and memoization |
| Best for listing selections | Best for count or optimization |
If every combination must be returned, output-sensitive exponential work is unavoidable.
Combinations vs Subsets
| Combinations | Subsets |
|---|---|
Fixed size k |
Any size from 0 to n |
Count is C(n,k) |
Count is 2^n |
Save only at size k |
Save at every recursion node |
| Stronger pruning possible | Usually explores all subset sizes |
Combinations vs Combination Sum
| Combinations | Combination Sum |
|---|---|
Select exactly k values |
Select values that reach a target |
| Each number normally used once | Candidate reuse may be allowed |
| Base condition is size | Base condition is remaining sum |
| Values come from a range or array | Values are candidate amounts |
Combination Sum is the next important extension of this pattern.
Senior-Level Follow-Up Questions
How Would You Generate Combinations in Lexicographic Order?
Use:
- Sorted input
- Standard forward backtracking
- Or an iterative index-array algorithm
Standard backtracking already produces lexicographic order when candidates are tried in ascending order.
How Would You Select k Items from Millions of Inputs?
Generating every combination is usually infeasible.
Possible alternatives:
- Sampling
- Greedy selection
- Optimization algorithms
- Constraint solving
- Dynamic programming
- Beam search
- Distributed evaluation
- Approximation algorithms
The correct approach depends on whether every combination is truly required.
Can Memoization Improve Combination Generation?
Not when all combinations must be returned.
Every valid path represents a distinct output.
Memoization helps more when the problem asks for:
- Number of valid combinations
- Existence of a valid combination
- Maximum or minimum score
- Target-sum counts
How Would You Preserve Input Objects Safely?
When combining mutable objects:
- Store immutable identifiers.
- Use immutable value objects.
- Avoid mutating selected elements.
- Copy objects when isolation is required.
Copying only the list does not deep-copy the objects inside it.
How Would You Add a Minimum or Maximum Sum Constraint?
Track the running sum.
For non-negative sorted values:
- Stop if the sum exceeds the maximum.
- Stop if even the largest possible remaining values cannot reach the minimum.
- Stop if too few candidates remain.
These bounds provide branch-and-bound pruning.
Strong Interview Explanation
Because order does not matter, I use a start index and only select values that come after the previously selected value. At each level, I add a candidate, recurse with the next candidate as the new start, and then remove the choice to restore state. When the current list reaches size
k, I copy it into the result. I also prune the loop so that I do not choose a starting value when too few values remain to complete the combination. The total time is O(k × C(n,k)) because there are C(n,k) outputs and each size-k result must be copied.
Interview Tips
Interviewers commonly ask:
- What is the difference between combinations and permutations?
- Why does the algorithm use a start index?
- Why recurse with
number + 1? - Why does order not create new combinations?
- Why must the current list be copied?
- How does pruning improve the search?
- How do you derive
n - needed + 1? - What is the time complexity?
- How do you handle duplicate input values?
- How do you generate only one valid combination?
- Can combinations be generated iteratively?
- Can the count be computed without generating results?
- What happens when
k = 0ork = n? - How would you process combinations lazily?
Unit Tests
import static org.junit.jupiter.api.Assertions.assertEquals;
import static org.junit.jupiter.api.Assertions.assertTrue;
import java.util.List;
import org.junit.jupiter.api.Test;
class CombinationsTest {
private final CombinationsOptimized solution =
new CombinationsOptimized();
@Test
void shouldGenerateAllPairsFromFourValues() {
List<List<Integer>> result =
solution.combine(
4,
2);
assertEquals(
6,
result.size());
assertTrue(
result.contains(
List.of(1, 2)));
assertTrue(
result.contains(
List.of(3, 4)));
}
@Test
void shouldHandleSingleCombination() {
List<List<Integer>> result =
solution.combine(
1,
1);
assertEquals(
List.of(List.of(1)),
result);
}
@Test
void shouldHandleSelectingAllValues() {
List<List<Integer>> result =
solution.combine(
4,
4);
assertEquals(
List.of(
List.of(1, 2, 3, 4)),
result);
}
@Test
void shouldHandleZeroSelection() {
List<List<Integer>> result =
solution.combine(
4,
0);
assertEquals(
List.of(List.of()),
result);
}
@Test
void shouldGenerateTenCombinations() {
List<List<Integer>> result =
solution.combine(
5,
3);
assertEquals(
10,
result.size());
}
}
Unit Tests for Array Combinations
import static org.junit.jupiter.api.Assertions.assertEquals;
import static org.junit.jupiter.api.Assertions.assertTrue;
import java.util.List;
import org.junit.jupiter.api.Test;
class ArrayCombinationsTest {
private final ArrayCombinations solution =
new ArrayCombinations();
@Test
void shouldGenerateArrayCombinations() {
List<List<Integer>> result =
solution.combine(
new int[]{10, 20, 30, 40},
2);
assertEquals(
6,
result.size());
assertTrue(
result.contains(
List.of(10, 20)));
assertTrue(
result.contains(
List.of(30, 40)));
}
@Test
void shouldHandleEmptySelection() {
List<List<Integer>> result =
solution.combine(
new int[]{1, 2, 3},
0);
assertEquals(
List.of(List.of()),
result);
}
}
Approach Comparison
| Approach | Time | Auxiliary Space | Main Advantage |
|---|---|---|---|
| Standard backtracking | O(k × C(n,k)) | O(k) | Clear and flexible |
| Pruned backtracking | O(k × C(n,k)) | O(k) | Avoids impossible branches |
| Include/exclude recursion | Up to O(2^n) traversal | O(n) | Shows binary decisions |
| Iterative construction | Output-sensitive | High allocations | Avoids recursion |
| Lexicographic generation | O(k × C(n,k)) | O(k) | Ordered iterative output |
Pruned for-loop backtracking is the preferred interview solution.
Summary
The Combinations problem extends the core backtracking pattern by selecting exactly k values while ignoring order.
The key design choice is the start index.
After selecting a number, recursion continues only with larger remaining numbers.
This ensures:
- No value is reused.
- Reordered duplicates are not generated.
- Every valid combination appears exactly once.
The optimized solution also prunes branches when too few candidates remain.
Complexity:
Time: O(k × C(n,k))
Auxiliary Space: O(k)
Output Space: O(k × C(n,k))
Key Takeaways
- A combination is an unordered selection.
- Order matters for permutations but not combinations.
- The number of size-
kcombinations isC(n,k). - Use a start index to prevent reordered duplicates.
- Recurse with the candidate’s next value.
- Follow choose–explore–unchoose.
- Copy the current list before storing it.
- Stop when the current size reaches
k. - Prune branches that cannot collect enough values.
- Use
n - needed + 1as the maximum candidate. - Sort and skip same-level duplicates for repeated input values.
- Generate lazily when storing every result is unnecessary.
- Calculate the binomial coefficient directly when only the count is required.
- Use dynamic programming or optimization methods when full generation is infeasible.
- This pattern prepares you for Combination Sum and constraint-based selection problems.