Distinct Ingredient Bundles
MediumBacktracking
Problem
A pantry holds items labelled by integers in nums; the same label may appear several times (three identical cans are all labelled 2).
Return every distinct bundle you can take from the pantry, including the empty bundle. Two bundles are the same if they contain the same labels the same number of times. Return them in any order.
Example 1
- Input:
- nums = [1, 2, 2]
- Output:
- [[], [1], [1, 2], [1, 2, 2], [2], [2, 2]]
Taking 'the first 2' or 'the second 2' gives the same bundle [2], so it appears once.
Example 2
- Input:
- nums = [0]
- Output:
- [[], [0]]
Constraints
- 1 ≤ nums.length ≤ 10
- -10 ≤ nums[i] ≤ 10
Hint
Show the first hint
Why does the plain include/exclude recursion produce duplicates here?
Walkthrough
How to approach it
01Clarify before coding
- Are [1, 2] and [2, 1] the same bundle? Yes, bundles are multisets.
- Is the empty bundle included? Yes.
- Can I reorder the input? Yes, only the bundles are returned.
02Brute force
Generate all 2^n subsets, sort each one, and deduplicate through a set of tuples.
Cost: O(n · 2^n · log n) time and O(n · 2^n) extra memory for the set; it explores [2, 2, 2]'s three single-2 subsets only to throw two away.
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.
This problem is part of Pro.