cf.completefrontend
RECURSION & BACKTRACKING · CORE

Generating subsets

List every group you can make by keeping or leaving out each item, from the empty group to the full one.

Time O(2^n × n)Space O(n)7 practice problemsStep-through picture

The idea

A subset is any group of items taken from a list, where order doesn't matter. From [1, 2, 3] you can make [], [1], [2], [3], [1, 2], [1, 3], [2, 3], and [1, 2, 3]. That is 8 subsets.

Each item is either in a subset or not. With n items that is two options, n times, so there are 2^n subsets. For 10 items that is 1,024, and for 20 items it is about a million.

The backtracking way to list them: every time you enter the search, the current path is itself a subset, so save it. Then try adding each later item, one at a time, and go deeper. Only adding items that come after the last one used means each group is built once, never twice in a different order.

An everyday example

Packing a lunch box from a row of snacks

Snacks sit in a row on the counter. You walk along the row from left to right. Every lunch box you have at any moment is a valid lunch, so you photograph it. Then you pick one snack further along the row, put it in, and keep walking from there. When you reach the end of the row, you take the last snack out and try the next one instead. You never walk back to the left, so you never pack the same set of snacks twice.

How the example maps to the code
In the exampleIn the code
Photographing the lunch box as it is nowresults.push([...path])
Snacks further along the rowfor (let i = start; ...)
Putting a snack in the boxpath.push(items[i])
Walking on from that snackexplore(i + 1)
Taking the snack back outpath.pop()

From the slow way to generating subsets

  1. A first idea: build groups by picking items one at a time in any order, then throw away the repeats. [6, 2] and [2, 6] are the same group, so you would sort each list and keep one copy. For 10 items this builds 9,864,101 ordered lists just to end up with 1,024 groups. Almost all of the work makes repeats.
  2. The waste comes from order. A group has many orders, but we only need one of them. So agree on a single order for every group: the order the items have in the input. Each group can then be written in exactly one way, and every other way of writing it is never built.
  3. To build only lists in input order, remember where the last pick was. A call gets a start index, and it may only add items from start onward. After adding items[i], the deeper call gets start = i + 1, so it can never reach back to an earlier item.
  4. One more thing is different from most backtracking: there is no "complete" length. Every list built this way, even the empty one, is already a valid group. So save a copy of path on entering each call, then try each later item. That loop of save, push, explore, pop is generating subsets.

How it works

  1. Keep results for the subsets and path for the subset being built.
  2. Write explore(start). start is the first index that may still be added.
  3. On entering explore, save a copy of path: it is already a valid subset.
  4. Loop i from start to the end. Add items[i] with path.push.
  5. Call explore(i + 1), so deeper calls only use items after i.
  6. Remove items[i] with path.pop() and continue the loop with the next item.
  7. Call explore(0) once and return results.

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.

Loading the picture…
See every step at onceThe same run, laid out side by side
Drawing every step…

The code

Point at a note to light up the lines it explains.

JavaScriptOpen in the code editor (opens in a new tab)
  1. function subsets(items) {
  2. const results = [];
  3. const path = [];
  4. function explore(start) {
  5. results.push([...path]);
  6. for (let i = start; i < items.length; i++) {
  7. path.push(items[i]);
  8. explore(i + 1);
  9. path.pop();
  10. }
  11. }
  12. explore(0);
  13. return results;
  14. }

How fast it is

TimeO(2^n × n)
Extra memoryO(n)

There are 2^n subsets and each copy takes up to n steps. Apart from the output, only path and the call chain are kept, each at most n long.

  • Best caseO(2^n × n)

    Every list of n items. There are always 2^n subsets holding n × 2^(n-1) items in total, so no input of that size is faster. For [6, 2, 8] that is 8 subsets and 12 items copied.

  • Average caseO(2^n × n)

    Any input. The values don't matter, only how many there are.

  • Worst caseO(2^n × n)

    Any input. For 20 items it saves 1,048,576 subsets holding 10,485,760 items in total.

Common mistakes

  • Calling explore(start + 1) instead of explore(i + 1). Deeper calls can reuse earlier items, which creates duplicates such as [2, 1] after [1, 2].
  • Saving path without copying it. All entries in results point to the same array, and they all end up empty.
  • Forgetting the empty subset. It is a valid answer, and the code above saves it on the very first call.
  • Skipping repeated values without sorting first. The duplicates are only next to each other after sorting.

When to use it

Look for these clues in a problem:

  • The question asks for "all groups", "all selections", or "every combination of any size".
  • Each item is either in or out, and the order inside a group doesn't matter.
  • The list is small, usually 20 items or fewer, because there are 2^n groups.
  • You need the best group by some score, and the input is small enough to check them all.

Check yourself

Answer each one in your head first, then open it.

How many times is explore called for 5 items?

32 times, the same as the number of subsets. Each call saves exactly one subset, and every subset comes from exactly one call.

Why is the copy saved when entering explore, not only at some full length?

Because every path, from [] to the full list, is already a valid subset. Saving only at a full length would return just one group.

For items = [6, 2, 8], why is [2, 6] never built?

6 is at index 0. After pushing 2 at index 1, the deeper call starts at index 2, so it can't go back to index 0.

What happens if you write explore(i) instead of explore(i + 1)?

The deeper call starts its loop at the same i, pushes items[i] again, and calls explore(i) again, forever. The call stack grows until the engine throws a RangeError.

Practice problems

Stuck on one? Tuto is in the playground too, and gives you hints, never the answer.

Not started

0 of 7 solved. Solve one to earn the bronze medal, half for silver, and all of them for gold.

Start practicing

easy

medium

hard

Go 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: when explore(start) is called, path lists items in increasing index order, and every index in it is below start. The first call has an empty path and start = 0, so the rule holds. A loop step pushes items[i] with i >= start and calls explore(i + 1), so the indexes still increase and all are below the new start. The pop after the call puts path back.

Every subset is saved. Take any group and list its indexes in increasing order, say i1 < i2. The first call's loop reaches i1 and pushes it. The call explore(i1 + 1) has a loop that reaches i2, because i2 > i1, and pushes it. The call after that saves the group. The empty group is saved by the very first call.

No subset is saved twice. Each call saves exactly once, and a call is reached by exactly one series of loop choices: the indexes in path, in increasing order. Two calls with the same set of indexes would need the same series, so they are the same call. There are 2^n groups and one call per group, so the search makes exactly 2^n calls and then ends.

Going deeper

3 more ideas

Why no subset appears twice

Inside every subset that the search builds, the items appear in the same order as in the input, because each deeper call only looks at indexes after the last one used. A group like {1, 3} can only be built as [1, 3], never as [3, 1]. So each group has exactly one way to be built, and it is saved exactly once.

Handling repeated items

With [1, 2, 2], choosing the first 2 or the second 2 gives the same group. Sort the items first, then inside the loop skip items[i] when i > start and items[i] === items[i - 1]. This lets a group use both 2s, but stops two loop steps at the same depth from starting with an equal value.

The cost

There are 2^n subsets, and copying each one takes up to n steps, so the time is O(2^n × n). The output alone has that size, so no method can be faster when you must list them all. The extra memory, apart from the output, is the path and the call chain, at most n deep.

Work it by hand

Every step in a table, with why

List every subset of 3 numbers that are not sorted. Each row is one call to explore, in the order the calls happen.

items = [6, 2, 8]

Stepstartpath savedLoop tries iWhat happensWhy
10[]0 to 2push 6, call explore(1)The first call saves the empty subset, then starts its loop with items[0] = 6.
21[6]1 to 2push 2, call explore(2)[6] is a subset, so it is saved at once. Only items after index 0 may be added.
32[6, 2]2push 8, call explore(3)The group keeps input order, [6, 2], even though 2 < 6. The code never sorts.
43[6, 2, 8]nonereturn, pop 8, pop 2, push 8start = 3 is past the end, so the loop is empty. Back in explore(1), the loop moves to i = 2.
53[6, 8]nonereturn, pop 8, pop 6, push 2Both loops below the top are done. The top call pops 6 and moves to i = 1.
62[2]2push 8, call explore(3)Groups starting with 2 may only add items after index 1, so 6 can't come back.
73[2, 8]nonereturn, pop 8, pop 2, push 8The top call moves to its last item, i = 2.
83[8]nonereturn, all loops doneNothing comes after index 2, so this is the last subset.

It returns [[], [6], [6, 2], [6, 2, 8], [6, 8], [2], [2, 8], [8]]: all 2^3 = 8 subsets, one per call. The search ends when the top call's loop has tried i = 0, 1, and 2.

Compared with other ways

When to pick something else
ApproachTimeExtra memoryChoose it when
Generating subsetsO(n · 2^n)O(n)You need every group listed and want an easy place to add pruning or a duplicate rule.
Bitmask loopO(n · 2^n)O(1)There are at most about 20 items and you want a flat loop, or you want to store each group as a single number.
Include or exclude recursionO(n · 2^n)O(n)You think of the problem as one yes-or-no decision per item, such as in knapsack-style searches.
Dynamic programming over sumsO(n · target)O(target)Only a count or a best value is asked, with a sum limit, so you never need to list the groups.

Extra memory: O(n) besides the output: path and the call chain are at most n deep. The output itself holds n × 2^(n-1) items, which is O(n × 2^n).

How the steps grow

1101001k10k100k1M116324864input size n
Steps as the input grows, for Generating subsets and the other approaches, on a scale where each line up is 10 times more steps.
  • Generating subsets, Bitmask loop, Include or exclude recursion O(n · 2^n)
  • Dynamic programming over sums O(n · target)
About how many steps for bigger inputs
Approachn = 10n = 1,000n = 1,000,000
Generating subsets10,240more than a quadrillionmore than a quadrillion
Bitmask loop10,240more than a quadrillionmore than a quadrillion
Include or exclude recursion10,240more than a quadrillionmore than a quadrillion
Dynamic programming over sums1001 million1 trillion

Inputs that need care

5 tricky inputs
An empty list: items = []
The first call saves [] and its loop never runs, so the answer is [[]]. One empty subset is correct.
Repeated values: items = [5, 5]
The code returns [[], [5], [5, 5], [5]], with [5] twice, because the two 5s are different indexes. Sort first and skip items[i] when i > start and items[i] === items[i - 1].
A larger list: 25 items
That is 33,554,432 subsets. The code is right, but the output won't fit in a browser tab. If you need the best subset or a count, use dynamic programming or prune while searching.
Objects as items: items = [{ id: 1 }]
[...path] copies the array, not the objects inside it. Every subset holding that object points to the same object, so changing it in one subset changes it everywhere.
Output order
Subsets come out in search order, not by size: [6, 2, 8] comes before [6, 8]. If you need them by size, sort results afterwards or run combinations once for each size.

Variations and follow-ups

Twists interviewers add

Include or exclude

Write explore(i) that decides item i only: call it once without items[i] and once with it, and save when i === items.length. It makes the same 2^n subsets in a different order, as the leaves of a binary tree.

Bitmask loop

Count mask from 0 to 2^n - 1; bit j of mask says whether items[j] is in the group. There's no recursion at all, and a subset can be stored as one number. It works up to about 30 items with 1 << j.

Subsets with repeated values

Sort items, then skip items[i] when i > start and it equals items[i - 1]. Two loop steps at the same depth can't start with the same value, but one group can still use both copies.

Subsets under a limit

To list groups whose sum stays within a budget, stop going deeper when adding items[i] would go over. If the items are sorted from small to large, you can break instead of continue, because every later item is at least as big.

In an interview

Spot it, explain it, answer follow-ups
  • Spot it from "all subsets", "every selection", "all groups of any size", or a limit like n <= 20. If order matters, it's permutations instead; if the size is fixed, it's combinations.
  • Say out loud: "every path is a valid answer, so I save on entry, and start keeps the items in input order so no group is built twice". That one sentence covers both correctness and duplicates.
  • Test [] (answer [[]]), one item (answer [[], [x]]), and two equal items to show you thought about repeats.
  • A usual follow-up is "do it without recursion". Start with [[]]; for each item, copy every subset so far and add the item to each copy. The list doubles for each item, giving 2^n subsets.

Where frontend code uses it

The same idea in real UI code
  • A filter panel with n checkboxes has 2^n possible states. Tests that try every state are generating subsets.
  • When a component has several optional boolean props, a visual test page that renders every on/off mix lists the subsets of those props.
  • Choosing which optional bundles or add-ons fit a budget in a pricing page is a subset search when the list is short.

Related algorithms