Subsets
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
Return every possible subset (the power set) of a list of distinct numbers, including the empty one.
3Hint ladder
Take one rung at a time. Stop as soon as the idea clicks.
- Hint 1How many subsets does a list of 3 items have? What happens to that count when you add a 4th item?
- Hint 2Every old subset can appear again with the new item added.
4The approach
Have you tried the hints? The approach is built as a path from the obvious way to the clever one.
Planning which friends come to a party. Start with the plan "nobody". When friend 1 is considered, every existing plan can exist with or without him, so you copy each plan and add friend 1 to the copy. Then friend 2: again every plan so far can exist with or without her. After all friends the list of plans is every possible guest list.
- The obvious way
Try every yes/no choice per item recursively: it is already optimal in output size, 2^n subsets.
- The key insight
Start with a list holding only the empty subset. For each number, make a copy of every subset already in the list with the number added, and append those copies. The list doubles each time.
- The algorithm
- subsets = [[]].
- Take the next number.
- For each subset already there, add a copy with this number.
- After the last number, return all subsets.
Watch it run
Examplenums = [1, 2, 3]
Start with the plan "nobody": [ ].
[ ]
Where people slip
- In Java read the size before the inner loop; growing the list while looping would never stop.
- Make a copy of each old subset before adding to it.
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(nums):
plans = [[]] # start with "nobody"
for number in nums:
plans += [plan + [number] for plan in plans] # every plan, with the new friend added
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.