Dynamic Programming Interview Question #1 - Find Sets Of Numbers That Add Up To 16

NOTE: There's an outline of this video in the comment section below!

[CSDojo]

Below is an outline of this video!

Also, here are a few links I thought you might like:

Outline:
0:00: Introduction to the problem
1:05: Clarifying questions you might ask
2:06: How I would approach this problem
3:54: How to solve this problem with recursion
6:48: A recursive solution in code
11:51: The problem with the recursive solution
12:28: A dynamic programming solution
16:12: The time complexity of the DP solution

[noobsdancing]

I've been trying dynamic programming problems for a few weeks and it felt like I was banging my head against a wall. Honestly, I thought I was too dumb to understand it. Something about this video made things click for me. Thank you!!!

[serhiypidkuyko]

Hi. Thank you for this task.
As for the code:
1.you don't need to check "if total<a[i]" because it's the same as "total-a[i]<0" and this case you already check in condition "if total<0" (two lines less in the code)
2.for the key it's better (I think) to choose a tuple (total, i), then you don't need to calculate the key (one line less in the code)
3.if you define the function "dp(arr, total, i, mem)" as a sub function of the function "count_sets_dp" then you can do it as "dp(total, i)" (two parameters less)
4.it;s better to check "if key in mem" after (not before) the basic checks (total==0, <0, i<0) because for these cases you know for sure you don't have items in the mem

[SR-tijj]

Really great video man. I've been programming for years, but could never really wrap my head around dynamic programming/developing recursive algorithms. This definitely helped me on my way. Thank you!

[arjitb]

The tree explanation for this problem really helped, turns out that most DP questions follow a similar tree to compute all possible subsets/permutations

[notgate]

3:50 made me laugh

You kept coming into frame from left and right then you just straight vsauce it.

[AlexanderMcNulty]

Hi, thank you! Best programming tutorials I’ve seen. In two videos on DP you have exposed me to a hefty bag of tricks. I can’t wait to practically apply what you have shown me. Thanks again!

[vishalchauhan-qmnp]

Give this man a bigger white board (Great Explanation though)

[theguildofsilence]

I was with you until about 4:30, then nothing made sense

[Raj_Patel]

You should count the time complexity on white board, It was a bit confusing for me to understand(can you give a better explanation for it for upcoming videos). But I understood the algorithm. Thanks man!!

[lazaronshyta]

2D array dynamic solution is easier to understand and implement, also it helps finding the logic of the recursive solution ( if you struggle in recursion), so checking 2d dp solution before moving to recursion is a good idea in this case

[rockyfan]

Why is the runtime O(total * n)?
Think about two test data:
[2, 4, 6, 10] total = 16, O(16 * 4) ?
[2000, 4000, 6000, 10000], total = 16000, O(16000 * 4)?

[arthuretf]

Nice video!

Just one suggestion in the final solution: it is not necessary to add the 4th condition (i.e. total < arr[i]). If that is the case, dp(arr, total - arr[i], i - 1, mem) will return 0 due to the 2nd condition.

However, I understand that by keeping the 4th condition you'll save a few insertions in the call stack, which is something that Python does not handle very efficiently.

[mstmar]

Your time complexity calculations are a bit off. If you call dp twice per per call, you end up with exponential growth. So without dynamic programing, you'd call the the function 2^n times, not n*2 times. with dp, you can sometimes lower this as there is only total*n possible values for "total:i", which makes the complexity O(min(2^n, total*n)).


Also, you don't really need to test if total < arr[i] as dp(arr, total - arr[i], i-1, mem) will trigger total < 0 and return 0 right away.

[Stumdra]

Minor point:
The 'else if total < 0' condition is kind of superfluous. It can only hit in the very first call from count_sets_dp and would be better placed there if you want to check for correct input. In the recursive function itself the 'else if total < arr[i]' condition assures that total doesn't fall below 0.

[emolieren]

wouldn't it be nicer to remove `total < arr[i]` condition branch and just let the to_return = (dp(arr, total - arr[i], i-1, mem) + dp(arr, total, i-1, mem)) since the first part will alway return 0 if total - arr[i] < 0?

[yashnagda]

This content is so valuable. I will even buy it if it was paid. 👍👍
Thanks!!

[tanaykulkarni]

Please try this

Supervin loves to eat candies. Today, his favorite candy shop is offering N candies, which are arranged in a line. The i-th candy in the line (counting starting from 1) has a sweetness level Si. Note that the sweetness level of a candy might be negative, which means the candy tastes bitter.

Supervin likes to eat sweet candies. However, candies with a combined sweetness level of more than D would be too much sweetness even for him. Supervin also realises that a candy with an odd sweetness level is "odd", and he does not want to eat more than O odd candies. In other words, an odd candy is a candy with a sweetness level that is not evenly divisible by 2. Additionally, since Supervin is in a rush, he can only eat a single contiguous subset of candies.

Therefore, he wants to eat a contiguous non-empty subset of candies in which there are at most O odd candies and the total sweetness level is maximized, but not more than D. Help Supervin to determine the maximum total sweetness level he can get, or return IMPOSSIBLE if there is no contiguous subset satisfying these constraints.

[djsalon]

Just want to share my solution which also prints out the subset/s:


val = 16

def subset2(arr, tot, out):

if(tot == val):
print(out)
return 1

if(tot > val): return 0

for i in range(len(arr)):
if i < len(arr):
return subset2(arr[i+1:], tot, out) + subset2(arr[i+1:], tot+arr[i], out + [arr[i]])

return 0

arr = [2, 4, 6, 10]
print(subset2(arr, 0, []))

[JCho-pijz]

I rarely give compliments bc I always have something that bothers me about the video (i don't compliment tech videos) but WOW!!!! you're exceptional. your videos are AMAZING!!!! I have a physics degree went into DS/ML like most of us do and now I'm switching to CS. Your videos are so clear cut your speech is impeccable, perfect pace, sound and visual, and a nice flow. I can tell you did multiple takes or practice (if not that's REALLY impressive). combined with all you have a great knowledge base and present it *flawlessly*. Most of my interviews were things you covered and your videos are also the right amount of time. It's short enough to maintain interest and long enough to give you thoroughly. It's kind of a shame that people will only really tune in during interviews or when they are learning CS/DS. You structured it well with depth and breadth. You go into a great overview and then have videos that go into more specific which is WAY better than having one long video. I wish I saw these videos before just doing a bunch of leetcode problems. It's a great clean organized way of explaining the tools. I didn't know how many leetcode problems were enough but this is great! I used your info so much on interviews. It's so memorable and keeps my attention (I have ADHD so I'm really picky with videos). I'll definitely share your channel with people interviewing or anyone new to coding. If you decide to leave YouTube please keep these videos up. Also, you don't have that annoying "Aren't you amazed how smart I am?" arrogant vibe. You have a very humble, enthusiastic energy. Okay, this comment is way too long it's kind of creepy, but I'm a girl so how dangerous can I be? I just really wanted to let you know your videos are powerful and I really appreciate the time you take to edit them, it makes watching/learning so much easier. I know it's a lot of effort and it might not be obvious to people watching bc we're so focused on learning but I thought you should know it sets you apart.