Every Topping Combination
EasyBacktrackingFree
Problem
A pizza shop labels each topping with a distinct integer id. Given the array nums of available ids, return every possible selection of toppings, from the plain pizza (no toppings) to the one with all of them.
Each selection is a list of ids. The selections may be returned in any order, and the ids inside a selection may be in any order.
Example 1
- Input:
- nums = [1, 2, 3]
- Output:
- [[], [1], [2], [3], [1, 2], [1, 3], [2, 3], [1, 2, 3]]
Each of the 3 toppings is either on or off, giving 2^3 = 8 selections.
Example 2
- Input:
- nums = [0]
- Output:
- [[], [0]]
Constraints
- 0 ≤ nums.length ≤ 10
- -10 ≤ nums[i] ≤ 10
- All values in nums are distinct.
Hint
Show the first hint
For each topping you make exactly one decision. What are the two choices?
Walkthrough
How to approach it
01Clarify before coding
- Is the empty selection included? Yes, the plain pizza counts.
- Can ids repeat? No, all values are distinct, so every selection is automatically unique.
- Does the output order matter? No, neither the order of selections nor the order inside one.
02Brute force
Count a mask from 0 to 2^n - 1 and, for each mask, pick the elements whose bit is set.
Cost: O(n · 2^n) time, which is optimal here because the output itself has 2^n lists; it works, but the interviewer usually wants the recursive decision-tree version that generalises to harder variants.
The rest of the walkthrough is in the app
The full walkthrough (key insight, step-by-step, dry run, complexity, edge cases, pitfalls, follow-ups) and solutions in Python and JavaScript are in the app, next to an editor and a terminal that runs your code against the tests.