Every Possible Topping Combo

TIP103 Unit 11 Session 1 (Click for link to problem statements)

Every Possible Topping Combo

A pizza shop lets a customer pick any subset of the distinct toppings in nums, including no toppings at all. Given the list of distinct toppings, return every possible combination.

Return a list of all subsets; the order of subsets does not matter.

def subsets(nums):
    pass

Problem Highlights

• 💡 Difficulty: Medium
• ⏰ Time to complete: 20-25 mins
• 🛠️ Topics: Subsets, Combinatorial Enumeration, Backtracking

1: U-nderstand

Understand what the interviewer is asking for by using test cases and questions about the problem.

• Established a set (2-3) of test cases to verify their own solution later.
• Established a set (1-2) of edge cases to verify their solution handles complexities.
• Have fully understood the problem and have no clarifying questions.
• Have you verified any Time/Space Constraints for this problem?

• Q: Should the empty combination (a pizza with no toppings) be included in the result?
  • A: Yes. The customer may pick no toppings at all, so the empty list [] must appear as one of the combinations.
• Q: Does the order of the subsets in the returned list matter?
  • A: No. Any ordering of the subsets is acceptable, as long as every possible combination appears exactly once.
• Q: Can the same topping appear more than once in a single combination?
  • A: No. The toppings in nums are distinct, and a combination either includes a given topping or it does not.

HAPPY CASE
Input: nums = [1, 2, 3]
Output: [[], [1], [2], [1, 2], [3], [1, 3], [2, 3], [1, 2, 3]]
Explanation: There are 2^3 = 8 possible combinations of 3 distinct toppings, including the empty combination.

EDGE CASE
Input: nums = []
Output: [[]]
Explanation: With no toppings available, the only possible order is a plain pizza, so the empty combination is the sole subset.

Input: nums = [7]
Output: [[], [7]]
Explanation: One topping yields exactly two combinations: skip it or take it.

2: M-atch

Match what this problem looks like to known categories of problems, e.g. Linked List or Dynamic Programming, and strategies or patterns in those categories.

For Generating All Subsets (the Power Set), we can consider the following approaches:

• Iterative Build-Up (Cascading): Start with only the empty subset, then for each topping, clone every subset built so far and append the new topping to the clones. Each topping doubles the number of subsets.
• Backtracking (DFS): For each topping make a binary include/exclude choice, recursing until every topping has been decided.

Both approaches enumerate the same 2^N subsets; the iterative build-up is used below because it maps directly onto the "each topping either joins a combo or doesn't" intuition.

3: P-lan

Plan the solution with appropriate visualizations and pseudocode.

General Idea: Begin with a list containing just the empty combination. Process the toppings one at a time: for each topping, every existing combination spawns one new combination that additionally includes this topping. After processing all N toppings, the list holds all 2^N subsets.

1) Initialize `combos` as a list containing one element: the empty list.
2) For each `topping` in `nums`:
   a) For every combination currently in `combos`, build a new list equal to
      that combination with `topping` appended.
   b) Add all of these new combinations to `combos`.
3) Return `combos`.

⚠️ Common Mistakes

• Forgetting to seed the result with the empty subset, which both loses [] and leaves nothing to extend.
• Mutating existing combinations in place (e.g. combo.append(topping)) instead of building a new list, corrupting subsets already collected.
• Appending to combos while iterating over it directly, which can cause an infinite loop; iterate over a snapshot (or build the new combos in a separate list) instead.

4: I-mplement

Implement the code to solve the algorithm.

def subsets(nums):
    combos = [[]]  # Start with the empty combo (no toppings)
    for topping in nums:
        # For every combo built so far, create a new combo that adds this topping
        combos += [combo + [topping] for combo in combos]
    return combos

5: R-eview

Review the code by running specific example(s) and recording values (watchlist) of your code's variables along the way.

• Input: nums = [1, 2, 3]

  • Start: combos = [[]]
  • After topping 1: combos = [[], [1]]
  • After topping 2: combos = [[], [1], [2], [1, 2]]
  • After topping 3: combos = [[], [1], [2], [1, 2], [3], [1, 3], [2, 3], [1, 2, 3]]
  • Output: [[], [1], [2], [1, 2], [3], [1, 3], [2, 3], [1, 2, 3]], matching the example.

• Input: nums = []

  • The loop never runs, so the seeded [[]] is returned directly.
  • Output: [[]]

6: E-valuate

Evaluate the performance of your algorithm and state any strong/weak or future potential work.

Assume N is the number of toppings in nums.

• Time Complexity: O(N * 2^N) because we generate 2^N subsets and copying each one when extending it costs up to O(N).
• Space Complexity: O(N * 2^N) for the output list itself, which stores 2^N subsets of average length N/2; no auxiliary space beyond the output is needed.