Generating combinations
List every way to choose exactly k items from a list, where the order of the chosen items doesn't matter.
O(C(n, k) × k)Space O(k)5 practice problemsStep-through pictureThe idea
A combination is a choice of exactly k items from a list, where order doesn't matter. Choosing 2 of [a, b, c, d] gives 6 combinations: ab, ac, ad, bc, bd, cd.
It works like subsets with one extra rule: only save a group when it has exactly k items. Each deeper call starts after the last item used, so ab is built but ba never is.
One more trick makes it fast: stop early when there aren't enough items left to reach k. If you still need 3 items and only 2 remain, no answer can grow from here, so the loop can end.
An everyday example
Picking a team of three from a line of players
Players stand in a line. You pick the team from left to right: once you pick a player, you only look at players to their right for the next pick. When the team has three players, you write it down, send the last pick back, and try the next player to the right. If you need two more players and only one is left in the line, you stop looking right away.
| In the example | In the code |
|---|---|
| The players picked so far | The path array |
| Only looking to the right of the last pick | explore(i + 1) |
| The team is full: write it down | if (path.length === k) |
| Too few players left to finish a team | items.length - i < k - path.length |
| Sending the last pick back | path.pop() |
From the slow way to generating combinations
- If you know
kahead of time, sayk = 3, three nested loopsi < j < llist every group of 3. Butkis an input, and you can't write a different number of nested loops for eachk. Another first idea is to list every subset and keep only those withkitems. For 20 items andk = 18, that builds 1,048,576 subsets to keep 190 of them. - Recursion replaces the nested loops. Each call is one loop level: it picks the next item from
startonward, and passesi + 1down so the next level only looks to the right, just likej > iin the nested loops. The depth of the recursion becomesk, whateverkis. - Since only groups of exactly
kitems count, save whenpath.length === kand return right away: going deeper could only make the group too big. That alone stops groups from growing pastk, but the search still walks into many starts that can never reachkitems. - Here's the waste: if you still need 3 items and only 2 are left in the list, nothing can be completed from here, and it only gets worse further right. So
breakout of the loop as soon asitems.length - i < k - path.length. For 20 items andk = 18, this drops the search from 1,048,555 calls to 1,330. That loop, with the early stop, is generating combinations.
How it works
- Keep
resultsand apath. Writeexplore(start), wherestartis the first index still allowed. - If
path.length === k, save a copy and return. - Loop
ifromstartto the end of the list. - If fewer items remain (
items.length - i) than are still needed (k - path.length), stop the loop. - Push
items[i], callexplore(i + 1), then pop it. - Call
explore(0)and returnresults.
Watch it run
This picture runs the code below on a real input. Press Step to move one step at a time, or Play to watch. The highlighted line is the one that just ran. Change the input to see other cases.
See every step at onceThe same run, laid out side by side
The code
Point at a note to light up the lines it explains.
function combinations(items, k) {const results = [];const path = [];function explore(start) {if (path.length === k) {results.push([...path]);return;}for (let i = start; i < items.length; i++) {if (items.length - i < k - path.length) break;path.push(items[i]);explore(i + 1);path.pop();}}explore(0);return results;}
How fast it is
| Time | O(C(n, k) × k) |
|---|---|
| Extra memory | O(k) |
There are C(n, k) groups and each copy takes k steps. Apart from the output, path and the call chain are at most k deep.
- Best case
O(1)kis bigger than the list, as incombinations([1, 2], 3): the first loop step sees 2 items left and 3 needed, breaks, and returns[]. - Average case
O(C(n, k) × k)Any normal
k: the early stop keeps the number of calls close to the number of groups. For 10 items andk = 3it makes 165 calls for 120 groups. - Worst case
O(C(n, k) × k)kis half ofn, which gives the most groups:C(20, 10) = 184,756groups of 10 items each.
Common mistakes
- Calling
explore(i)when items may not be reused. The same item gets picked twice, giving groups like[1, 1]. - Saving groups smaller than
k. Only save whenpath.length === k. - Using
continueinstead ofbreakin the early stop. It's still correct, but it keeps looping over items that can never help. - In target-sum variations, not sorting before skipping repeated values. The skip only works when equal values sit next to each other.
When to use it
Look for these clues in a problem:
- The question says "choose
k", "pick exactlyk", or "all groups of sizek". - Order inside a group doesn't matter:
[1, 2]and[2, 1]are the same answer. - The question asks for all groups whose items add up to a target, sometimes with items that may be reused.
- The answer must avoid duplicate groups even though the input has repeated values.
Check yourself
Answer each one in your head first, then open it.
For items = ["p", "q", "r", "s"] and k = 3, how many groups are saved and how many times does the loop break?
4 groups and 3 breaks, as the trace shows. The breaks happen at [p] with i = 3, at [q] with i = 3, and at the top with i = 2.
Why is break correct in the early stop, rather than continue?
The number of items left only shrinks as i grows. If the group can't be filled from index i, it can't be filled from any later index either.
How many groups does combinations([3, 6, 9, 12, 15], 3) return?
10, which is C(5, 3) = 5 × 4 × 3 / 6. The first is [3, 6, 9] and the last is [9, 12, 15].
If items may be reused, why must the early stop be removed?
With reuse, a single item can fill all the spots, so the number of items left no longer limits the group. Keeping the check makes the search break before it finds groups like [2, 2, 2].
Practice problems
Stuck on one? Tuto is in the playground too, and gives you hints, never the answer.
0 of 5 solved. Solve one to earn the bronze medal, half for silver, and all of them for gold.
Start practicingGo further
You don't need these to start practicing. Open one when you want more.
Why it works
The reasoning that makes it always right
The rule is the same as for subsets: path lists items in increasing index order, and the call explore(start) may only add items at start or later. So a group like {p, r, s} has exactly one way to be built, p then r then s, and is saved at most once.
The early stop never loses a group. From index i, there are items.length - i items left, counting items[i] itself. If that is less than k - path.length, the group can't be filled from here. Every later i leaves even fewer items, so none of them can fill it either, which is why break is safe and continue would only waste loop steps.
Every group is found, and the search ends. Take a group's indexes in increasing order. At each depth, the loop reaches the group's next index, and the early stop can't fire before it: that index and the group's later indexes are all still ahead, so enough items remain. The depth never goes past k, and each loop moves right, so the search ends after the top loop breaks or runs out.
Going deeper
3 more ideas
Why groups come out once and in order
Inside each saved group, items keep their input order, because each deeper call starts after the index just used. So the group {a, c} has only one way to be built: a first, then c. And because the loop goes left to right, the groups come out in sorted order when the input is sorted.
Target-sum variations
A common variation picks groups whose values add up to a target. Keep a running remaining value instead of a fixed k. Save the group when remaining === 0, and stop when it goes below zero. If each item may be reused, call explore(i) instead of explore(i + 1). If the input has repeats but each item is used once, sort first and skip items[i] when i > start and it equals items[i - 1].
How many groups there are
Choosing k of n items gives C(n, k) = n! / (k! × (n - k)!) groups. C(10, 3) = 120 and C(20, 10) = 184,756. Each group is copied in k steps, so the time is O(C(n, k) × k). The early stop doesn't change that bound, but it removes many dead branches in practice.
Work it by hand
Every step in a table, with why
Choose 3 of 4 letters. Each row is one turn of a for loop: either a push or the early stop.
items = ["p", "q", "r", "s"], k = 3
| Step | path before | i | items.length - i | k - path.length | What happens | Why |
|---|---|---|---|---|---|---|
| 1 | [] | 0 | 4 | 3 | push p | 4 items are left and 3 are needed, so p can start a group. |
| 2 | [p] | 1 | 3 | 2 | push q | The deeper call starts at i = 1, to the right of p. |
| 3 | [p, q] | 2 | 2 | 1 | push r, save [p, q, r] | path reaches 3 items, so the next call saves a copy and returns without looping. |
| 4 | [p, q] | 3 | 1 | 1 | push s, save [p, q, s] | One item left and one needed: just enough. |
| 5 | [p] | 2 | 2 | 2 | push r | Back to the second spot, now trying r. |
| 6 | [p, r] | 3 | 1 | 1 | push s, save [p, r, s] | The only item to the right of r completes the group. |
| 7 | [p] | 3 | 1 | 2 | 1 < 2: break | Only s is left but 2 more are needed. p, s can never become a full group, so the loop stops. |
| 8 | [] | 1 | 3 | 3 | push q | Every group with p is done. Now groups that start with q. |
| 9 | [q] | 2 | 2 | 2 | push r | Exactly enough items are left. |
| 10 | [q, r] | 3 | 1 | 1 | push s, save [q, r, s] | The last group. |
| 11 | [q] | 3 | 1 | 2 | 1 < 2: break | q, s can't be completed, so stop. |
| 12 | [] | 2 | 2 | 3 | 2 < 3: break | Starting at r leaves only 2 items for 3 spots. The top loop ends, so the search is over. |
It returns [["p", "q", "r"], ["p", "q", "s"], ["p", "r", "s"], ["q", "r", "s"]], which is C(4, 3) = 4 groups. The 3 breaks stopped the search from walking into starts like [r] and [p, s], which could never be completed.
Compared with other ways
When to pick something else
| Approach | Time | Extra memory | Choose it when |
|---|---|---|---|
| Generating combinations | O(n^3) | O(k) | For k = 3 it does about C(n, 3) × 3 steps, close to the output size. It works for any k and has an easy place for sum limits and duplicate rules. |
| Three nested loops | O(n^3) | O(1) | k is fixed and small, like pairs or triples. It's the simplest code when you know k while writing it. |
Subsets, then keep size k | O(n · 2^n) | O(n) | Almost never. It builds every subset of every size to keep a few, which is why the early stop exists. |
Bitmask loop, keep masks with k bits | O(n · 2^n) | O(1) | n is at most about 20 and you already loop over masks for another reason. |
Extra memory: O(k) besides the output: path and the call chain are at most k deep. The output holds C(n, k) × k items.
How the steps grow
- Generating combinations, Three nested loops
O(n^3) - Subsets, then keep size
k, Bitmask loop, keep masks withkbitsO(n · 2^n)
| Approach | n = 10 | n = 1,000 | n = 1,000,000 |
|---|---|---|---|
| Generating combinations | 1,000 | 1 billion | more than a quadrillion |
| Three nested loops | 1,000 | 1 billion | more than a quadrillion |
Subsets, then keep size k | 10,240 | more than a quadrillion | more than a quadrillion |
Bitmask loop, keep masks with k bits | 10,240 | more than a quadrillion | more than a quadrillion |
Inputs that need care
5 tricky inputs
k = 0path.length === kis true on the first call, so it saves[]and returns[[]]. There is one way to choose nothing.kbigger than the list:combinations([1, 2], 3)- The first loop step breaks because 2 items are left and 3 are needed. It returns
[]without pushing anything. kequal to the list length:combinations([7, 8, 9], 3)- At every depth, the remaining items exactly match the need, so the search goes straight down once and returns
[[7, 8, 9]]. - Repeated values:
combinations([2, 2, 3], 2) - It returns
[[2, 2], [2, 3], [2, 3]], with[2, 3]twice. Sort first and skipitems[i]wheni > startand it equalsitems[i - 1]. kclose ton: 20 items,k = 18- There are only 190 groups. The early stop keeps the search to 1,330 calls. You can also choose the 2 items to leave out, since
C(n, k) = C(n, n - k).
Variations and follow-ups
Twists interviewers add
Groups that add up to a target
Track a remaining sum instead of a size. Save when remaining === 0, and stop when it goes below zero. If the items are sorted from small to large, you can break as soon as items[i] is bigger than remaining.
Items that may be reused
Call explore(i) instead of explore(i + 1), so the same item can be picked again. Remove the size-based early stop too: with reuse, one item can fill every spot. Leaving it in makes combinations with reuse of [1, 2] and k = 3 return [] instead of 4 groups.
Next combination without recursion
Keep an array of k indexes, starting at [0, 1, ..., k - 1]. To move to the next group, find the rightmost index that can still move right, add one to it, and reset every index after it to follow it in a row. This lists the groups in the same order as the recursion.
Counting groups only
When the question only asks how many groups exist, use C(n, k) = C(n - 1, k - 1) + C(n - 1, k), which builds Pascal's triangle in O(n × k) steps, or multiply and divide in a loop.
In an interview
Spot it, explain it, answer follow-ups
- Spot it from "choose
k", "all groups of sizek", "pick exactlyk", or "all teams ofkplayers", where order inside a group doesn't matter. - Explain the two rules out loud:
explore(i + 1)keeps items moving right so each group is built once, and the early stopitems.length - i < k - path.lengthcuts starts that can't be completed. - Test
k = 0,kequal to the list length, andkbigger than the list. Each needs no special code, and saying why shows you understand the base case. - The common follow-up is the target-sum version with reuse: switch to
explore(i), drop the size check, and stop when the running sum goes past the target.
Where frontend code uses it
The same idea in real UI code
- Checking color contrast for every pair of colors in a palette means looking at every combination of 2 colors.
- Cross-browser test plans pick combinations of browsers, screen sizes, and themes. Pairwise testing tools reduce that list but start from the same idea.
- Collision checks between
ndraggable cards look at every pair of cards, which isC(n, 2)pairs.