You need to explore combinations of optional features. Each feature can be included or left out. The examples are small, but the choices branch quickly.

Recursion gives each smaller decision the same shape as the larger one. Backtracking adds a discipline: make a choice, explore what follows, then restore the state before trying the alternative.

The restoration step is where many otherwise sensible solutions go wrong.

Define what one call owns

Let visit(index) explore every subset that can be formed from the remaining items, given the choices already stored in chosen.

At each index, there are two branches: leave the item out, or put it in. When the index reaches the input length, the current choices describe one complete subset.

The function must leave chosen exactly as it found it before returning to its caller. That is the promise that makes sibling branches independent.

Take a snapshot at the leaf

function subsets(values) {
  const results = [];
  const chosen = [];

  function visit(index) {
    if (index === values.length) {
      results.push(chosen.slice());
      return;
    }
    visit(index + 1);
    chosen.push(values[index]);
    visit(index + 1);
    chosen.pop();
  }

  visit(0);
  return results;
}

The first recursive call explores subsets that omit the current item. The second explores subsets that include it. The final pop restores the earlier path.

The copy at the leaf is equally important. Saving chosen itself would save a reference to one mutable array that continues changing. Earlier results would not be stable snapshots.

This function treats input positions as distinct choices. For ['a', 'a'], two different selections can produce the same value sequence. If you want unique value-based subsets, define and implement that additional requirement.

Trace a two-item input

For ['map', 'search'], the omit/include branches produce [], ['search'], ['map'], and ['map', 'search'] in that order.

Returning from the branch containing both features removes search. Returning from the branch rooted at map removes map. Every branch starts with exactly the choices made by its ancestors, with no leftovers from its siblings.

This resembles depth-first traversal, although the search tree here is generated by decisions rather than stored in an adjacency list. Each call explores a branch before returning to try another.

The number of answers already costs something

There are 2^n position-based subsets for n items. Producing all of them cannot take linear time. This implementation also copies each selected path. Across all subsets, that gives O(n × 2^n) output construction work and output storage.

The recursion stack and current path use O(n) auxiliary space apart from results. A generator or callback can avoid retaining every result at once, but it does not remove the amount of output that a caller requests.

A recursive function is not inherently slow. The branching structure and repeated subproblems determine the work. A single recursive walk down a list is very different from exploring every subset.

Prune only when the reason is sound

Suppose every feature has a positive cost and you only need combinations within a budget. Once the current total exceeds that budget, adding more positive costs cannot repair the branch, so you can stop exploring it.

If negative costs are allowed, that argument no longer holds: a later negative cost might bring the total back down. A pruning condition is a proof about what future choices can do, not just a convenient if statement.

For production-sized inputs, also consider recursion depth and cancellation. A mathematically finite search can still be far too large to finish within a user’s patience or a server’s resource budget.

Practice: generate fixed-size selections

How would you return only subsets containing exactly three items?

Work through useful pruning rules

Record a result as soon as chosen.length === 3, then stop that branch. Stop when the input is exhausted before reaching three. You can also stop when the number of remaining items is smaller than the number still needed.

The state now includes the position and the current selection size. Keep the push/explore/pop discipline unchanged. If the input contains fewer than three positions, there are no results; for a requested size of zero, the empty selection is one valid result.