Problem 556665 · medium · Phase 05 Advanced Algorithms & Graphs

Distinct Topping Bundles

backtracking · subsets · duplicates · sorting

A pizza counter has a tray of toppings, some of which appear several times. The tray is given as a list of integers tray (equal numbers are identical toppings). A bundle is any selection of toppings from the tray, including the empty bundle. Return every distinct bundle as a list of integers in non-decreasing order. Bundles may be returned in any order, but no bundle may appear twice.

Examples

Input:  tray = [2, 2, 5]
Output: [[], [2], [2, 2], [2, 2, 5], [2, 5], [5]]
Explanation: [2, 5] is one bundle no matter which of the two 2s is used.

Input:  tray = [4]
Output: [[], [4]]

Input:  tray = []
Output: [[]]

Constraints

  • 0 <= len(tray) <= 10, 1 <= tray[i] <= 20
  • At most 1024 bundles are possible.

Goals

  • Enumerate subsets of a multiset without producing the same bundle twice
  • Skip a candidate equal to the one just un-chosen at the same level
Starting Python…