Burger Truck Test Orders

EasybacktrackingAlso known as Subsets

A burger truck lets customers add any of its extra toppings, each at most once. Before opening day, the owner wants to ring up every possible burger on the new till to make sure the prices come out right: the plain burger, every burger with one topping, every pair, all the way up to the one with everything.

Two burgers with the same toppings are the same burger, whatever order the toppings were added in. Produce the full test list.

Your task

Write allOrders(toppings). toppings is a list of different topping names. Return a list containing every possible selection of toppings exactly once, including the empty selection (the plain burger).

Each selection is a list of topping names. The selections can be in any order, and the toppings inside a selection can be in any order.

allOrders(toppings: string[]) → string[][] Several answers can be correct; any valid one is accepted.

Examples

Example 1

Input

toppings = ["cheese", "onion", "pickle"]

Output

[[], ["pickle"], ["onion"], ["onion", "pickle"], ["cheese"], ["cheese", "pickle"], ["cheese", "onion"], ["cheese", "onion", "pickle"]]

Why

Each topping is either on the burger or not, so 3 toppings give 2 × 2 × 2 = 8 burgers. The plain burger [] counts, and ["onion", "cheese"] would be the same burger as ["cheese", "onion"], so it must not appear twice.

Example 2

Input

toppings = []

Output

[[]]

Why

With no toppings on the menu there is still one burger to ring up: the plain one. So the answer is a list holding one empty selection, not an empty list.

Constraints

0 ≤ toppings.length ≤ 10
All topping names are different, non-empty strings.
Selections and the toppings inside them may be returned in any order.

Start with brute force

The first instinct is nested loops: one loop for single toppings, two nested loops for pairs, three for triples. But the number of nested loops would have to match the size of the menu, and you cannot write a different number of loops for every input. Recursion is the way to get "one loop level per topping".

Speed is not the issue here: the answer itself holds 2ⁿ selections, so no method can beat O(n · 2ⁿ). Counting in binary from 0 to 2ⁿ − 1 and reading each bit as "topping in or out" is just as fast. The recursive version is worth learning because the same skeleton still works when later problems add rules about which choices are allowed.

Hints

0 of 4 shown

Hint 1
List every burger for the menu ["cheese", "onion"] by hand. For each burger you wrote, what did you decide about cheese, and then about onion?
Hint 2
Every burger comes from one yes/no decision per topping, made in menu order. 3 toppings means 3 decisions with 2 options each, so 8 burgers. The decisions form a tree that splits in two at each topping.
Hint 3
Write a recursive helper choose(i) that makes the decision for topping i: first explore the burgers without it, then the burgers with it, each time moving on to i + 1. When i reaches the end of the menu, every decision is made and you have one finished burger.
Hint 4
Keep one shared list current. To explore "with topping i", push it, call choose(i + 1), then pop it so the list is back to how it was. When i equals the menu length, store a copy of current, because the same list keeps changing afterwards.

Walkthrough and solution

Unlocks when you pass every test. Stuck for a while? Looking is fine too, as long as you then close it and write the code yourself.

How to solve it

Turn "list every burger" into "make one yes/no decision per topping". Recursion walks the tree of decisions, and one shared list records the decisions on the current path.

Trace ["cheese", "onion"]. Read each line as the path of decisions so far:

Cheese: no. Onion: no. End of menu, record [].
Back up to onion. Push onion, record ["onion"], pop it.
Back up to cheese. Push cheese. Onion: no, record ["cheese"].
Push onion, record ["cheese", "onion"], pop onion, then pop cheese.

Four burgers, each found once, and current is empty again at the end. The two lines that make this work are the copy when recording (without it every stored burger is the same list, which ends empty) and the pop after the "with" branch (without it toppings leak into later burgers).

Reference solution

function allOrders(toppings) {
  const orders = [];
  const current = []; // the burger being built
  function choose(i) {
    if (i === toppings.length) {
      orders.push([...current]); // copy: current keeps changing
      return;
    }
    choose(i + 1);               // burger without topping i
    current.push(toppings[i]);
    choose(i + 1);               // burger with topping i
    current.pop();               // undo before going back up
  }
  choose(0);
  return orders;
}

def all_orders(toppings):
    orders = []
    current = []  # the burger being built
 
    def choose(i):
        if i == len(toppings):
            orders.append(current[:])  # copy: current keeps changing
            return
        choose(i + 1)                  # burger without topping i
        current.append(toppings[i])
        choose(i + 1)                  # burger with topping i
        current.pop()                  # undo before going back up
 
    choose(0)
    return orders

TimeO(n · 2ⁿ)There are 2ⁿ selections, and copying each one costs up to n.

SpaceO(n)The recursion depth and the current list are at most n, not counting the output of 2ⁿ selections.

Learn the idea: Backtracking Recursion

Ctrl+Enter runs

Run your code to see results here. Run checks the examples. Submit checks every test, including hidden edge cases.

Write code