Subsets II
1Try it yourself first
Think for 20-30 minutes before you open any hint. Being stuck is where the learning happens.
Only for you, saved in this browser. After you see the approach you will compare it with your idea.2What is being asked
Same as subsets, but the list can contain duplicates. Return every unique subset.
3Hint ladder
Take one rung at a time. Stop as soon as the idea clicks.
- Hint 1Sort the numbers first. What goes wrong with [2, 2] in plain subsets?
- Hint 2When this number equals the previous one, which subsets should you extend?
4The approach
Have you tried the hints? The approach is built as a path from the obvious way to the clever one.
Same party, but now two identical twins may come. If the twin joins every old plan again, you would write "1 twin" twice. So the second twin only joins the plans that were created when the FIRST twin arrived; those are the only plans that are new in this round.
- The obvious way
Generate all subsets and remove duplicates with a set: works but wasteful.
- The key insight
Sort. Keep track of how many subsets existed before the previous number was added. If the current number differs from the previous one, extend ALL subsets; if it is the same, extend only the subsets created in the previous round.
- The algorithm
- Sort the numbers; plans = [[]].
- For a new value: extend every plan.
- For a repeat of the previous value: extend only the plans added in the last round.
- Return plans.
Watch it run
Examplenums = [1, 2, 2]
Start: [ ]. First number 1 is new: extend all. Plans: [ ], [1].
[ ], [1]
Where people slip
- Forgetting to sort lets equal numbers sit apart and breaks the rule.
How close was your idea?
You did not write an idea, and that is fine.
Be honest with yourself. This sets your revision list.
5Code
Try writing it yourself from the steps first. Then compare.
def subsets_with_dup(nums):
nums.sort() # equal numbers sit together
plans = [[]]
previous_size = 0 # how many plans existed before the last number
for index, number in enumerate(nums):
first = previous_size if index > 0 and number == nums[index - 1] else 0
previous_size = len(plans)
for plan in plans[first:previous_size]: # a repeat extends only last round's new plans
plans.append(plan + [number])
return plansNow close this and write it again from memory, in the language you will use in the interview. Reattempt after 1 day, 7 days and about 30 days.
6Still stuck? Watch a video
Seeing someone explain it out loud can make it click. Try the video after you have read the approach above.