Nice!! Here is an idea -> You can club some problems to have super similar code. It will be better for understanding the concepts! Example: The problem in this video is SUPER similar to coin change II. The only change is, here we loop through amount or "target" first and then through coins or "nums". Intuition: If we parse through coins first, we consider every coin only once -> We will miss the unique combination. If we parse through target first, we can consider coins again and again -> We can protect unique combinations count. Try this code on this problem and it will pass to remember its similarity with coin change II (make sure to change the input params to the function when you run), def combinationSum4(self, coins: List[int], amount: int) -> int: dp = [0] * (amount + 1) dp[0] = 1 for i in range(1, amount + 1): for j in range(len(coins)): if i - coins[j] >= 0: dp[i] += dp[i - coins[j]] return dp[-1] Here are the set of problems that can use this unbounded knapsack pattern : Coin change 1, Coin Change 2, Perfect Squares, Combination Sum 1, 2, 3, 4
Yeah I came up with same solution .Insane , how some problems like LIS and Coin Change , can be beneficial to solve other problems , gives a different perspective to do DSA altogether !
In the tree, each number is repeated with different paths, and those are the combinations for adding upto the number, This combination of paths is the subproblem, which can be derived for n with path 1 + subproblem of (n-1), path 2 + subproblem of (n-2) etc.
I'm broken now sir , I got rejected by amazon yesterday , even though I give my best efforts , I lost it .... But I thanks to you sir , I learned new methods and tricks by your videos , Thank You so much !!!!!!!
If you think this is a new method. No surprise rejection, man. There are at least 10+ questions on leetcode that are similar to (DFS + cache) and DP as far as I know.
One way to explain dp[0] is, it represents the specific case of target = 0, nums = [] -> 1 solution of emptiness -> 0. It's easier to think about it if you use an array for dp, not a hashmap. I'm not sure why he says you need a 2D array; 1D is sufficient. Still, very succinct solution overall, thank you!
Excellent videos ❤️ Plz try to make more and more videos on all recursion based topics like dp, backtracking, divide and conquer,graphs etc. Thankyou in advance😍
This can be thought of as a general fibonacci method. Instead of adding the last two, we take an array to determine indices of the previous values to add
Could you please explain how we made dp[0] = 1? For [1,2,3], there are no ways we can make the target sum = 0. The # of ways should be 0. Do you mean that we take none of the elements from the array [], that we count as one of the way?
I don't get this either, if the empty set were a combination, then id get it but (0) does not count as a combination so whether top down or bottoms up dp, not sure why it equals 1. Please expound
think about it using the provided example, but now adding an element equal to the target sum: ``` Input: nums = [1,2,3,4], target = 4 Output: 8 Explanation: The possible combination ways are: (1, 1, 1, 1) (1, 1, 2) (1, 2, 1) (1, 3) (2, 1, 1) (2, 2) (3, 1) (4) Note that different sequences are counted as different combinations. ``` The interesting thing in there is that we can choose _any_ number of elements from the input array. If you notice sometimes we choose 4 by repeating the numbers, sometimes 3, sometimes even a single element. The point is that choosing _any_ element also includes choosing *none*. So, if the target sum is 0, there will always be a combination available, which is choosing nothing from the nums list.
Why is DP[4] = D[4-1] + DP[4-2] + DP[4-3]? I understand if we were to find ways to get to a certain target, the only way we'll be able to get there is by using the elements from the nums array but that doesn't mean they'll all actually sum up to 4 though right? having a hard time wrapping my head around it
def combinationSum4(self, nums: List[int], target: int) -> int: nums.sort() memo ={} def buildTarget(current): if current in memo: return memo[current] if current > target: return 0 if current == target: return 1 count = 0 for i in range(len(nums)): next_val = current+nums[i] if next_val > target: break count += buildTarget(next_val) memo[current] = count return memo[current] buildTarget(0) return memo[0] if we use recursion, then solution can look something like this
Shouldn't the space complexity of the top-down recursion be O(T) where T is the target number. This is what Leetcode solution section say for this approach: Space Complexity: O(T) Due to the recursive function, the algorithm will incur additional memory consumption in the function call stack. In the worst case, the recursive function can pile up to T times. As a result, we would need O(T) space for the recursive function. In addition, since we applied the memoization technique where we keep the intermediate results in the cache, we would need additionally O(T) space. To sum up, the overall space complexity of the algorithm is O(T) + O(T) = O(T).
The initial decision tree explanation was understandable but I got little confused in DP solution- why is DP[0] = 1 ? since we need to go to the base case, so we need, DP[4] = DP[4-1]+DP[4-2]+DP[4-3]+DP[4-4] ? Explanation of the code part . Can someone please help me out in this
I understand that from the recursive solution. we know the base cases are two: 1. target = 0, we get 1 combination. 2. target < 0, we get 0 conbinations, right? see, that is why dp[0] == 1. Also, your example also can explain why dp[0] == 1. I guess your example is nums = [1,2,3,4], target = 4, because you said "DP[4] = DP[4-1]+DP[4-2]+DP[4-3]+DP[4-4]". If you draw that decision tree, in the 1st layer, the last one should be target = 0, that is one possible combination. So dp[0] = 1. In this kind of problem, if target is 0, that means putting nothing is also one combination. I know it is a little confused, but if you see some similar problems like this one, you willl see. Just keep that in mind. I hope both of them can help you understand why dp[0] = 1.
@@danielsun716 What a convincing explanation, thanks a lot😄. I will draw and do it manually on pen-paper to trace as per your explanation and then will re-attempt this problem😃.
Heres my memoized approach if anyones intrested: mem={} def dfs(i,t): if (i,t) in mem: return mem[(i,t)] if t==target: return 1 if targettarget: return 0 if i==len(nums): return 0
mem[(i,t)]= dfs(0,t+nums[i])+dfs(i+1,t) #RESET BACK TO 0 return mem[(i,t)]
If anyone wants the C++ code: int combinationSum4(vector& nums, int target) { vectordp(target+1,0); dp[0]=1; for(int i=1;i=0) dp[i]=dp[i]+dp[i-num]; } } return dp[target]; } Stats: Runtime: 0 ms, faster than 100.00% of C++ online submissions for Combination Sum IV. Memory Usage: 6.7 MB, less than 65.95% of C++ online submissions for Combination Sum IV.
@@raghavendrac4710 Yes that's because when you use simple int then in some test cases the overflow condition will be encountered so inorder to increase our domain of the vector we use unsigned int as it increases the limit. In simple words just to save the code from throwing an int overflow error
Why can't we use the concept of unbounded knapsack in this problem? As we can use each number multiple times to find target which is similar to unbounded knapsack.
The main difference between this and unbounded knapsack (like coin change 2) is that here different sequences are counted as different permutations (unbounded knapsack would count 1,1,2 as 1 combination, but here it expects 1,1,2 ; 1,2,1 ; 2,1,1 -> so 3 combinations
class Solution: def combinationSum4(self, nums: List[int], target: int) -> int: dp = [0] * (target + 1) dp[0] = 1 for i in range(1, target + 1): for num in nums: if i >= num: dp[i] += dp[i - num] return dp[target]
Nice!! Here is an idea -> You can club some problems to have super similar code. It will be better for understanding the concepts! Example:
The problem in this video is SUPER similar to coin change II. The only change is, here we loop through amount or "target" first and then through coins or "nums".
Intuition: If we parse through coins first, we consider every coin only once -> We will miss the unique combination. If we parse through target first, we can consider coins again and again -> We can protect unique combinations count.
Try this code on this problem and it will pass to remember its similarity with coin change II (make sure to change the input params to the function when you run),
def combinationSum4(self, coins: List[int], amount: int) -> int:
dp = [0] * (amount + 1)
dp[0] = 1
for i in range(1, amount + 1):
for j in range(len(coins)):
if i - coins[j] >= 0:
dp[i] += dp[i - coins[j]]
return dp[-1]
Here are the set of problems that can use this unbounded knapsack pattern :
Coin change 1, Coin Change 2, Perfect Squares, Combination Sum 1, 2, 3, 4
Yeah I came up with same solution .Insane , how some problems like LIS and Coin Change , can be beneficial to solve other problems , gives a different perspective to do DSA altogether !
The jump from recursion tree to bottom-up was too quick to comprehend, didn't get it.
Same
In the tree, each number is repeated with different paths, and those are the combinations for adding upto the number, This combination of paths is the subproblem, which can be derived for n with path 1 + subproblem of (n-1), path 2 + subproblem of (n-2) etc.
@@dheepthaaanand1133 I dont quite get why dp[0] = 1
@@cinimodmil If your target is 0, then it can only be achieved in one way - that is, by not picking any of the numbers.
@@crushed_oreos appreciate it, thank you!
I'm broken now sir , I got rejected by amazon yesterday , even though I give my best efforts , I lost it .... But I thanks to you sir , I learned new methods and tricks by your videos , Thank You so much !!!!!!!
If you think this is a new method. No surprise rejection, man. There are at least 10+ questions on leetcode that are similar to (DFS + cache) and DP as far as I know.
One way to explain dp[0] is, it represents the specific case of target = 0, nums = [] -> 1 solution of emptiness -> 0. It's easier to think about it if you use an array for dp, not a hashmap. I'm not sure why he says you need a 2D array; 1D is sufficient. Still, very succinct solution overall, thank you!
Excellent videos ❤️
Plz try to make more and more videos on all recursion based topics like dp, backtracking, divide and conquer,graphs etc.
Thankyou in advance😍
This can be thought of as a general fibonacci method. Instead of adding the last two, we take an array to determine indices of the previous values to add
Could you please explain how we made dp[0] = 1?
For [1,2,3], there are no ways we can make the target sum = 0. The # of ways should be 0.
Do you mean that we take none of the elements from the array [], that we count as one of the way?
Yes, he himself was confused about it.
You are right dp[0]=1 because we are considering empty array as 1 solution.
@@AsliArtistVlogs Thanks!
C++ Recursive code. Easy to understand.
class Solution {
public:
int combinationSum4(vector& nums, int target) {
return helper(nums, target);
}
int helper(const vector& nums, int target) {
if (target == 0) {
return 1;
}
int count = 0;
for (int num : nums) {a
if (target - num >= 0) {
count += helper(nums, target - num);
}
}
return count;
}
};
Why is dp[0] equal to 1?
0 is the base case; it means you find 1 solution. If you use recursive, your base case should be 0 return 1 & negative numbers return 0.
I don't get this either, if the empty set were a combination, then id get it but (0) does not count as a combination so whether top down or bottoms up dp, not sure why it equals 1. Please expound
I agree, if we ask ourselves "how many ways can we sum up to 0" as we did with dp[4], then dp[0] would be 0, the intuition is thrown off
think about it using the provided example, but now adding an element equal to the target sum:
```
Input: nums = [1,2,3,4], target = 4
Output: 8
Explanation:
The possible combination ways are:
(1, 1, 1, 1)
(1, 1, 2)
(1, 2, 1)
(1, 3)
(2, 1, 1)
(2, 2)
(3, 1)
(4)
Note that different sequences are counted as different combinations.
```
The interesting thing in there is that we can choose _any_ number of elements from the input array. If you notice sometimes we choose 4 by repeating the numbers, sometimes 3, sometimes even a single element. The point is that choosing _any_ element also includes choosing *none*.
So, if the target sum is 0, there will always be a combination available, which is choosing nothing from the nums list.
@@KarlJahn This is it, that's the explanation I was looking for, thank you!
Why is DP[4] = D[4-1] + DP[4-2] + DP[4-3]? I understand if we were to find ways to get to a certain target, the only way we'll be able to get there is by using the elements from the nums array but that doesn't mean they'll all actually sum up to 4 though right? having a hard time wrapping my head around it
same question...why do we have that formular ? is it always correct ?
def combinationSum4(self, nums: List[int], target: int) -> int:
nums.sort()
memo ={}
def buildTarget(current):
if current in memo:
return memo[current]
if current > target:
return 0
if current == target:
return 1
count = 0
for i in range(len(nums)):
next_val = current+nums[i]
if next_val > target:
break
count += buildTarget(next_val)
memo[current] = count
return memo[current]
buildTarget(0)
return memo[0]
if we use recursion, then solution can look something like this
I think you should have explained more thoroughly as to why we have to initialize dp[0]? I struggled to follow at first before I drew it out in Paint.
Shouldn't the space complexity of the top-down recursion be O(T) where T is the target number.
This is what Leetcode solution section say for this approach:
Space Complexity: O(T)
Due to the recursive function, the algorithm will incur additional memory consumption in the function call stack. In the worst case, the recursive function can pile up to T times. As a result, we would need O(T) space for the recursive function.
In addition, since we applied the memoization technique where we keep the intermediate results in the cache, we would need additionally O(T) space.
To sum up, the overall space complexity of the algorithm is O(T) + O(T) = O(T).
The initial decision tree explanation was understandable but I got little confused in DP solution-
why is DP[0] = 1 ?
since we need to go to the base case, so we need, DP[4] = DP[4-1]+DP[4-2]+DP[4-3]+DP[4-4] ?
Explanation of the code part .
Can someone please help me out in this
I understand that from the recursive solution. we know the base cases are two: 1. target = 0, we get 1 combination. 2. target < 0, we get 0 conbinations, right? see, that is why dp[0] == 1.
Also, your example also can explain why dp[0] == 1. I guess your example is nums = [1,2,3,4], target = 4, because you said "DP[4] = DP[4-1]+DP[4-2]+DP[4-3]+DP[4-4]". If you draw that decision tree, in the 1st layer, the last one should be target = 0, that is one possible combination. So dp[0] = 1.
In this kind of problem, if target is 0, that means putting nothing is also one combination. I know it is a little confused, but if you see some similar problems like this one, you willl see. Just keep that in mind.
I hope both of them can help you understand why dp[0] = 1.
@@danielsun716 What a convincing explanation, thanks a lot😄. I will draw and do it manually on pen-paper to trace as per your explanation and then will re-attempt this problem😃.
@@danielsun716 great explanations. Never thought about DP[0] is equal to target=0, the result is [], that's count as 1
Great explanation, thanks!
Thanks!
Heres my memoized approach if anyones intrested:
mem={}
def dfs(i,t):
if (i,t) in mem: return mem[(i,t)]
if t==target: return 1
if targettarget: return 0
if i==len(nums): return 0
mem[(i,t)]= dfs(0,t+nums[i])+dfs(i+1,t) #RESET BACK TO 0
return mem[(i,t)]
return dfs(0,0)
If anyone wants the C++ code:
int combinationSum4(vector& nums, int target) {
vectordp(target+1,0);
dp[0]=1;
for(int i=1;i=0) dp[i]=dp[i]+dp[i-num];
}
}
return dp[target];
}
Stats:
Runtime: 0 ms, faster than 100.00% of C++ online submissions for Combination Sum IV.
Memory Usage: 6.7 MB, less than 65.95% of C++ online submissions for Combination Sum IV.
hey can you explain why vector words for dp and vector doesnt work?
@@raghavendrac4710 Yes that's because when you use simple int then in some test cases the overflow condition will be encountered so inorder to increase our domain of the vector we use unsigned int as it increases the limit. In simple words just to save the code from throwing an int overflow error
Thanks for the code.
Is the dp cache the same thing as memoization?
yes exactly
@@NeetCode Thanks
Thanks bro thanks a lot, hope you continue this good work :3
How would you do this if we are counting combinations instead of permutations
This will be a question similar to coin change 2
Why can't we use the concept of unbounded knapsack in this problem? As we can use each number multiple times to find target which is similar to unbounded knapsack.
The main difference between this and unbounded knapsack (like coin change 2) is that here different sequences are counted as different permutations (unbounded knapsack would count 1,1,2 as 1 combination, but here it expects 1,1,2 ; 1,2,1 ; 2,1,1 -> so 3 combinations
Thank you very much!💜
Shouldn’t the name of this problem be permutation sum?
Love your channel! Can you please explain leetcode 1326 Minimum Number of Taps to Open to Water a Garden?
OP Explanation
You are awesome!
Thanks how do you write on the screen please share the setup thanks
Ham unbounded knapsack ka concept use kar sakte hain na
can u make a video on this?
#1235 - Maximum profit in job scheduling - HARD
class Solution:
def combinationSum4(self, nums: List[int], target: int) -> int:
dp = [0] * (target + 1)
dp[0] = 1
for i in range(1, target + 1):
for num in nums:
if i >= num:
dp[i] += dp[i - num]
return dp[target]
JAVA CODE -> leetcode.com/problems/combination-sum-iv/discuss/1966109/JAVA-SOLUTION-Top-Down-Approach-with-explanation
This will fail when the interviewer changes the question to add in float values
So what you suggest? How this problem should be solved if there will be float values?
whats a float value? like a decimal? there's only integers in this question
Thanks = float("inf") to you 💜