I rerecorded this solution and made it much better, please watch this instead: kzfaq.info/get/bejne/fLWphdN_urmqlXU.html
@saidjahonmamirov7355 Жыл бұрын
I solved it without using a for loop as it made more sense for me. But, this combines all of neetcodes previous solutions on subsets II and combinations: def combinationSum2(self, candidates: List[int], target: int) -> List[List[int]]: def backtrack(i, path, total): if total == target: res.append(path[:]) return if i >= len(candidates) or total > target: return path.append(candidates[i]) backtrack(i+1, path, total + candidates[i]) path.pop() while i+1 < len(candidates) and candidates[i] == candidates[i+1]: i = i + 1 backtrack(i+1, path, total) candidates.sort() res = [] backtrack(0, [], 0) return res
@sellygobeze7173 Жыл бұрын
thanks
@ijustdey Жыл бұрын
Hi there. Putting the base case (i >= len(candidates) or total > target) before the other base case (total == target) gives a wrong answer. Does anyone know why this is so?
@zhuofanli9985 Жыл бұрын
@@ijustdey I encountered the same issue. Taking candidates = [1, 2, 2, 2, 5] and target = 5 as example, using pythontutor for a visualization, I found out that's because if at the last recursion step, we append 5 (the last element) to path, and we call backtrack(i + 1, path, sum), immediately the algorithm found out i + 1 is greater than the length of the candidates array, so we'll never be able to append the single [5] to our result array.
@patrickbateman3912 Жыл бұрын
by using two temp arrays ??
@biancafuu11 ай бұрын
Hi, I also came up with a solution similar to this. I am really confused why its quite a bit slower to neetcode's solution. just wondering if anyone knows why, thanks
@manuchehrqoriev7 ай бұрын
Great explanation. for me it was easier to use logic of previous Neetcode solutions. It is not as fast as yours but easier to understand. Thanks brother for making such content :) class Solution: def combinationSum2(self, candidates, target): res = [] candidates.sort() def dfs(i, cur, total): # Base cases if total == target: res.append(cur.copy()) return if i >= len(candidates) or total > target: return cur.append(candidates[i]) dfs(i + 1, cur, total + candidates[i]) cur.pop() while i + 1 < len(candidates) and candidates[i + 1] == candidates[i]: i += 1 dfs(i + 1, cur, total) dfs(0, [], 0) return res
@xinniu31452 жыл бұрын
this is great, but still struggling to understand why this works LOL
@danny65769 Жыл бұрын
Neetcode used the "include/exclude" approach in his "combination sum" and "subsets II" solutions. In his approach with the current ("combination sum II") problem, he used a for-loop instead. In this approach, he is implicitly excluding the current element (and adding this to the result set) before the for loop. Within the for-loop, he is explicitly including the current element (this will be added to the result set in the next recursive call). I believe his solutions in "combination sum" and "subset II" were easier to understand.
@abhimanyuambastha25955 ай бұрын
@@danny65769 There are two methods of recursion to solve the problem. One is this one where you include or exclude a number at each recursive call. The second way is to do recursion over ALL possible combinations. This is the for loop method. Both have a slightly different decision tree, but are so similar that go with whatever is more intuitive
@anthonykugel56133 ай бұрын
It's a combination of sorting the candidates array and keeping track of the value of the previous candidate.
@ARkhan-xw8udАй бұрын
same here bro
@siqb3 жыл бұрын
Again a brilliant explanation. Two of the optimizations to stop searching if the values or sums get bigger than target were not included in the code so this runs a bit faster: class Solution: def combinationSum2(self, candidates: List[int], target: int) -> List[List[int]]: candidates.sort() res, curr = [], [] def backtrack(curr, pos, remain): if remain == 0: return res.append(curr[:]) prev = -1 for i in range(pos, len(candidates)): if prev == candidates[i]: continue elif remain - candidates[i] < 0: break curr.append(candidates[i]) backtrack(curr, i + 1, remain - candidates[i]) curr.pop() prev = candidates[i] backtrack(curr, 0, target) return res
@jamesvoynow35599 ай бұрын
Neetcode you're the man, and I will always come back to your videos. I hope this doesn't come across rude as I have a ton of respect for you, but I want to say that this coding explanation was not up to your typical high standards. Just wanted to give some hopefully helpful feedback if you were looking to re-do some of these tutorials.
@vvsish88032 жыл бұрын
For the people who wants Combination - 1 Style (***Credit - Halal Milksheikh ) Kill it :) class Solution: def combinationSum2(self, candidates: List[int], target: int) -> List[List[int]]: res=[] candidates.sort() def dfs(curr,i,tot): if tot==target: res.append(curr.copy()) return if i>=len(candidates) or tot>target: return curr.append(candidates[i]) dfs(curr,i+1,tot+candidates[i]) curr.pop() while i+1
@user-ek4ol8bk2s2 жыл бұрын
Thank you very much!
@pranavaskumar93078 ай бұрын
Can you please explain the while loop part?
@gowtham80603 ай бұрын
@@pranavaskumar9307that part skips the duplicate elements
@bandit825819 күн бұрын
@@pranavaskumar9307 It is to skip duplicates candidates = [10,1,2,7,6,1,5] For example, this case, there are 2 1s, therefore, it will get 2 [1,7] solution
@Mohammad-wo7yi2 жыл бұрын
I think the time complexity should be O(n * 2^n) instead of O(2^n) since we do a copy of the solution array at the end of every path. Actually it’s so weird for me that this problem’s time complexity is said to be O(2^n) while a very similar problem like Subset II is only O(n * 2^n).
@yohoyu66762 жыл бұрын
I have the same question, think these 2 problem have almost identical solution. but I am confused why we count the copy, do we count the copy whenever the solution is found by appending lists?
@brenomatos3526 Жыл бұрын
Agreed.
@DavidDLee Жыл бұрын
Your videos are *usually* very good at explaining the algorithm. This one is not. Looks like you explained one algorithm and coded another. In particular, in the decision tree (7:32) you have one branch which can choose 1s and another that may not include any 1s. There's no place in the code where you never use the same value again, as you backtrack with i + 1 (the next candidate can be the same value as current), which means that there's no such branch as never use 1 again.
@reggiehurley1479 Жыл бұрын
yep, which is interesting cause usually he likes to code up the binary decision tree. guess he just got mixed up 😅
@The6thProgrammer9 ай бұрын
While this isn't Neetcode's best video, you are incorrect in your statement that the algo doesn't match the tree. Take an input such as [1, 1, 2, 3] of candidates, with an arbitrary target value. The first call to backtrack will include [1], when the recursive stack is popped off and returns back to this original call, the for loop is used to then move i forward to index 2, which corresponds to value 2, so that the next call to backtrack (which we can consider the right branch) starts with [2] and will never choose a 1. This same concept holds recursively throughout the algorithm. Just because we don't call backtrack() twice in the for loop, we are still using the for loop to create a binary split each time we call cur.pop(), where the "right" split excludes what we included on the "left" in our prior call.
@CharlesMacKay888 ай бұрын
he skips duplicates if the candidate is from the same depth. e.g. the root node is 1, by using the prev variable. he initializes it to -1 such that on the recursion call, it will now be initialized back to -1 so on a different depth its not skipped, and skipping if prev == current candidate, meaning it was examined already on the current depth of the recursion. he avoid re-using the same number twice by doing the i+1 into the pos variable. this means we cannot re-use the variable since we no longer have access to it when recursing
@rahul9110172 жыл бұрын
Code that reuses Neetcode's concept from Combination Sum 1. A lot easier to remember the pattern. class Solution { List result; public List combinationSum2(int[] candidates, int target) { result = new ArrayList(); if (candidates == null || candidates.length == 0) { return result; } Arrays.sort(candidates); List currSet = new ArrayList(); dfs(candidates, 0, currSet, target); return result; } private void dfs(int[] candidates, int index, List currSet, int target) { // good base case if (target == 0) { List currCopy = new ArrayList(currSet); result.add(currCopy); return; } // bad base cases if (target < 0) { return; } if (index >= candidates.length) { return; } // two decisions: we can add this current number to our result // or we can ignore this number and do a dfs for the next number currSet.add(candidates[index]); // this first branch will have all the subsets which contain this currently added number // we can add this number again so index is not changed dfs(candidates, index + 1, currSet, target - candidates[index]); // backtrack currSet.remove(currSet.size() - 1); // skip duplicates while (index + 1 < candidates.length && candidates[index] == candidates[index + 1]) { index += 1; } // second branch will have all the subsets which dont have this current number dfs(candidates, index + 1, currSet, target); } }
@harshgandhi66932 жыл бұрын
Hey Rahul - Thanks for the solution. Your solution matches exactly with the explanation in the video (even better than the solution shown in the video. lol). Here is the python version of your solution class Solution: def combinationSum2(self, candidates: List[int], target: int) -> List[List[int]]: candidates.sort() res = [] def dfs(i, comb, t): if t == 0: res.append(comb.copy()) return if i == len(candidates) or t < 0: return dfs(i+1, comb + [candidates[i]], t - candidates[i]) while i+1 < len(candidates) and candidates[i+1] == candidates[i]: i = i + 1 dfs(i+1, comb, t) dfs(i=0, comb=[], t=target) return res
@melissac48722 жыл бұрын
@@harshgandhi6693 Thank you so much. You save me
@farazahmed72 жыл бұрын
Mkc kya solution dia majja agaça
@bokaixu65292 жыл бұрын
@@harshgandhi6693 Hi Harsh, Thank you so much for this answer. Helps a lot. Just wonder how to explain the time and space complexity of this function? Thank you. I am new to coding.
@tonynguyen45592 жыл бұрын
@@bokaixu6529 I wish I was able to do leetcode mediums when I was new LOL
@abhishekpawar84582 жыл бұрын
Reverse Sorting will help here : We hit the cases where the target is exceeded first. Thus, prune helps here
@tempestofsouls56932 жыл бұрын
Good catch
@adithyanvinod8342Ай бұрын
class Solution: def combinationSum2(self, candidates: List[int], target: int) -> List[List[int]]: res = [] candidates.sort() def dfs(i,cur): if sum(cur) == target: res.append(cur[::]) return if sum(cur) > target or i >= len(candidates): return for j in range(i,len(candidates)): if j>i and candidates[j] == candidates[j-1]: continue cur.append(candidates[j]) dfs(j+1,cur) cur.pop() dfs(0,[]) return sorted(res) i found this better and more easy to understand
@uniquename2386 Жыл бұрын
For ones who want similar solution from the first Combination Sum (I used JavaScript in this case): var combinationSum2 = function(candidates, target) { candidates.sort((a, b) => a - b) const res = [] function dfs(pos, cur, total){ if(total === target){ res.push([...cur]) return } if(pos === candidates.length || total > target){ return } cur.push(candidates[pos]) dfs(pos + 1, cur, total + candidates[pos]) while(pos + 1 < candidates.length && candidates[pos] === candidates[pos + 1]){ pos++ } cur.pop() dfs(pos + 1, cur, total) } dfs(0, [], 0) return res };
@ijustdey Жыл бұрын
Hi there. Putting the base case (i >= len(candidates) or total > target) before the other base case (total == target) gives a wrong answer. Does anyone know why this is so?
@uniquename2386 Жыл бұрын
What if your index exceeded the length of the array AND your total equals target? You would want to append the answer and return. That's why you would put the statement (total == target) first.@@ijustdey
@ijustdey Жыл бұрын
@@uniquename2386 hmm thank you. This is the first question out of various backtracking problem I’ve had to consider that. Normally I usually put the return base case first. Then check if we have our result.
@uniquename2386 Жыл бұрын
Glad it helped 😃 @@ijustdey
@Sedri149 ай бұрын
This is what I did too. I think it's easier than what he showed here
@13naman2 жыл бұрын
For those who didn't understand how [1,1,6] is reached, when traversing the first 1, we are backtracking for the next index, there initial 1 will be used. For the second iteration of for loop, we will have only one 1. Reply if it doesn't make sense.
@shavitl.3062 жыл бұрын
Hi, thanks- I didn't get it yet. How come the next 1 won't be skipped due the "continue" in the condition candidates[i] == prev?
@melissac48722 жыл бұрын
@@shavitl.306 same dont get it. Did you get it?
@anonymouswalrus107 Жыл бұрын
@@melissac4872 its cuz prev is initialized within the recursive function itself, when you call the recursive function again, the new instance of the recursion will have prev = -1 and curr=[1] (already including the first 1)
@SmoothCode9 ай бұрын
I dont get it. Why do we need to skip duplicates? They said we can use duplicate numbers that exist in the array right?
@oxyht Жыл бұрын
The code for combination 1 and while loop from subsets 2 is muh easier.
@tanishbansal105829 күн бұрын
based of combination sum 1 and subset 2 : class Solution: def combinationSum2(self, candidates: List[int], target: int) -> List[List[int]]: res = [] candidates.sort() def dfs(i,cur,total): if total == target: res.append(cur.copy()) return if i >= len(candidates) or total > target : return cur.append(candidates[i]) dfs(i+1, cur, total + candidates[i]) cur.pop() while i + 1 < len(candidates) and candidates[i] == candidates[i+1]: i += 1 dfs(i + 1, cur, total) dfs(0,[],0) return res
@Mohammad-wo7yi2 жыл бұрын
Why didn’t you solve it like your solution for Subset II?
@arashkoushkebaghi14326 ай бұрын
check out his Subset | problem and modify the code to solve this one. It's obvious he just memorize the solution from others and makes the videos out of it. he is just good at explaining the approach that he copied from the solution sections. NO hate, his videos are being helpful to me but he does not necessarily takes the time to solve the problem himself like the most of us. so... yeah
@nameunknown0072 жыл бұрын
Remembering previous element and all that, you made this program look different from the combination sum 1 program. The only change that can be done from the combination sum 1 program is the second recurse call can just take index from the next non-duplicate element. just a one liner change from sum-1.
@mertkahyaoglu482 жыл бұрын
Definitely, that's why I'm so confused with this approach as I'm coming from the first problem.
@halahmilksheikh2 жыл бұрын
What's the one line change? You have to sort it at least right?
@TheElementFive3 жыл бұрын
Hey man, just wanted to say you’re doing amazing things on this channel. Btw, do you have longest palindromic subsequence on your to-do list? Thanks!
@NeetCode3 жыл бұрын
Sure, I'll try to do it soon
@codingstation77413 жыл бұрын
Here's a trick: if you know LCS, longest palindrome subsequence is just LCS(string a, reverse(string a)).
@ShivamSharma_blogs2 жыл бұрын
@@codingstation7741 nice
@VanshChaudhary-yd5cp7 ай бұрын
@@codingstation7741 I really love this insight
@andresivanmonterocassab54862 жыл бұрын
Combining the solution of combinationSum1 and subsets2: def combinationSum2(self, candidates: List[int], target: int) -> List[List[int]]: # n = len(candidates) , t = target, min_c = min(candidates) # Time O( n ^ (t/min_c + 1) + nlog(n)) = > O( n ^ (t/min_c + 1)) # Space O(t/min_c) ans = [] curr_sum = [] candidates.sort() def backtrack(idx, total): if total == target: ans.append(curr_sum[:]) return if idx >= len(candidates) or total > target: return # left choice curr_sum.append(candidates[idx]) backtrack(idx + 1, total + candidates[idx]) curr_sum.pop() # right choice while idx + 1 < len(candidates) and candidates[idx] == candidates[idx + 1]: idx = idx + 1 backtrack(idx + 1, total) backtrack(0, 0) return ans
@gladyouseen81602 жыл бұрын
The code is diff from what you explained 😣. Explained include or exclude approach but coded iterated version
@codeplug Жыл бұрын
I think this question is a hard (though it is marked medium) one until one knows the trick. If given in an interview for the first time I'll probably use a set to avoid duplicate combination but that will surely exceed the time limit.
@markolainovic Жыл бұрын
But why would that exceed the time limit? Adding a tuple to the set should be as expensive as performing the copy of the list and appending it, and we can return a set as final result, LeetCode won't complain. You're right, btw, but I'm not sure why.
@richardnorth1881 Жыл бұрын
TLE will be caused because repeated work will be done (the same sub-problems will be needlessly re-computed)
@halahmilksheikh2 жыл бұрын
Ok for the people who want a Combination Sum I style of solution for this problem you gotta do 3 things. Sort the candidates, call i+1 on your first dfs and then before your second dfs, advance the pointer past the duplicates like this while (i + 1 < candidates.length && candidates[i] == candidates[i + 1]) { i++ }
@sureshg12 жыл бұрын
Thank you, This is what i was looking for. Its also confusing when explanations between combination 1 and 2 problems are so similar, that the solution is implemented so differently. Would be good to know why different solution approaches are needed or used.
@halahmilksheikh2 жыл бұрын
@@sureshg1 I dislike having the for loop in this answer because backtracking is already hard to understand and if you embed that iterating forloop, it's even more confusing, not to mention keeping track of the prev. I still don't understand how exactly it works. That's why I prefer the double dfs way because it closely models the decision tree and you don't have to think as much. Not just that but the double dfs template can be use for combo sum I/II and subsets I/II so it's very flexible.
@VarunMittal-viralmutant2 жыл бұрын
@@halahmilksheikh Actually, he used that approach in SubsetII question here: kzfaq.info/get/bejne/jNRiqZmSz6ebhWQ.html I am wondering, why the current prev == num approach doesn't work with SubsetII though. Any ideas ?
@halahmilksheikh2 жыл бұрын
@@VarunMittal-viralmutant I think it should work with subsets II. Keep in mind that in this current video, neet made a few typos that he fixed near the end.
@VarunMittal-viralmutant2 жыл бұрын
@@halahmilksheikh No it doesn't work. I think it needs an extra line of code for subset problem to work. Check the comment I made under that problem.
@financewithsom4852 жыл бұрын
your explanation and code are different you explained based on include or not in a level but coded in loop for each level
@hung-wenchen49462 жыл бұрын
agree. his recursion tree is diff from his code. his code obviosuly is not 2 brach tree, it's n-ary tree
@nachiket9857 Жыл бұрын
Exactly, was confused over this
@vijayakumareyunni6010 Жыл бұрын
Good attempt. But, it's unclear how we ended up with [1,1,6] if previous and current elements are the same.
@CS_n00b10 ай бұрын
the 1's are added in different function calls
@NhanSleeptight2 жыл бұрын
Do you think it's better to try to reuse the code of Combination Sum 1 for this question (just adding a while loop to check for sorted duplicates)?
@rahul9110172 жыл бұрын
Yep would be easier if we could just reuse the code for CS1. I added my code for that as a comment here.
@Sedri149 ай бұрын
That's what I did, I think it's easier: def combinationSum2(self, candidates: List[int], target: int) -> List[List[int]]: res = [] candidates.sort() def dfs(i, cur_comb, total): if total == target: res.append(cur_comb.copy()) return if total > target or i >= len(candidates): return cur_comb.append(candidates[i]) dfs(i + 1, cur_comb, total + candidates[i]) cur_comb.pop() # jump on all duplicates j = i while j < len(candidates) and candidates[j] == candidates[i]: j = j + 1 dfs(j, cur_comb, total) dfs(0, [], 0) return res
@gauravsinghtanwar44152 жыл бұрын
Optimisation which gives memory usage less than 87% of the submitted sols def get_combination(start,target,temp): prev=-1 for i in range(start,length): if candidates[i]==prev: continue if target-candidates[i]=0: temp.append(candidates[i]) if target-candidates[i]==0: ans.append(temp[:]) temp.pop() return get_combination(i+1,target-candidates[i],temp) temp.pop() else: return prev=candidates[i] ans=[] candidates=sorted(candidates) length=len(candidates) get_combination(0,target,[]) return ans
@CharlesMacKay888 ай бұрын
this one was tricky due to skipping duplicates. I like the usage of the prev variable. this made it very clean and logically solid.
@abheykalia34092 жыл бұрын
The way I understood the reqt for prev is that practically we are using different counts of the same element and brute forcing and prev==candidates[I] helps to avoid choose a permutation for the elements chosen
@homyakMilashka10 ай бұрын
Very well worded, thanks. This skip all ones trick is a difference between TLE and accepted.
@matthewsaucedo247110 ай бұрын
For those looking for a solution that is still python, but commented with easy to grasp rationale: class Solution: def combinationSum2(self, candidates: List[int], target: int) -> List[List[int]]: candidates.sort() combos = [] combo = [] def backtrack(i=0, localSum=0): # Base cases if localSum == target: combos.append(combo.copy()) return if i == len(candidates) or localSum > target: return # Spawn decision tree for choosing current index. # Reset the decision after (pop) combo.append(candidates[i]) backtrack(i+1, localSum + candidates[i]) combo.pop() # Advance index to the next non-equal digit to avoid duplicates, # then spawn a tree with the null decisiong (same target). while i+1 < len(candidates) and candidates[i+1] == candidates[i]: i = i + 1 backtrack(i+1, localSum) backtrack() return combos
@mehershrishtinigam5449 Жыл бұрын
Instead of this, you can just add a while loop to skip over the duplicate elements, like so - (Basically an udpated version of the Combination Sum I code, in C++) class Solution { public: void dfs(int i, vector cur, int total, vector &res, int &target, vector &candidates){ if(total == target){ res.push_back(cur); return; } if(i >= candidates.size() or total > target) return; cur.push_back(candidates[i]); dfs(i + 1, cur, total + candidates[i], res, target, candidates); cur.pop_back(); while(i < candidates.size()-1 and candidates[i] == candidates[i+1]) i++; dfs(i + 1, cur, total, res, target, candidates); } vector combinationSum2(vector& candidates, int target) { vector res; sort(candidates.begin(), candidates.end()); dfs(0, {}, 0, res, target, candidates); return res; } };
@nikhilgoyal007 Жыл бұрын
If there were two options at every spot, why is there just one backtrack function in the code and not two ? In the final code, it seems like the only backtrack function used will skip over similar values but I do not see the one that should use the same values ?
@minciNashu2 жыл бұрын
Python version of modified Combination Sum 1 def combinationSum2(self, candidates: List[int], target: int) -> List[List[int]]: res = [] candidates.sort() def bt(subset, pos, t): # base cases if t == 0: res.append(subset[:]) return if t < 0 or pos >= len(candidates): return # left subset.append(candidates[pos]) bt(subset, pos + 1, t - candidates[pos]) # right, skip completely until distinct candidate subset.pop() while pos + 1 < len(candidates) and candidates[pos] == candidates[pos + 1]: pos += 1 bt(subset, pos + 1, t) bt([], 0, target) return res
@rocmewtwo4 ай бұрын
you can use most of the same code in 90. Subsets II. the concept of two problems is how to deal with duplicates.
@ramirez6127 Жыл бұрын
I solved it using the patterns of both Combination Sum and Subsets II class Solution { public void dfs(int i, List combination, List combinations, int[] candidates, int sum, int target) { if (sum == target) { combinations.add(new ArrayList(combination)); return; } if (sum > target || i >= candidates.length) return; combination.add(candidates[i]); dfs(i + 1, combination, combinations, candidates, sum + candidates[i], target); combination.remove(combination.size() - 1); while (i + 1 < candidates.length && candidates[i + 1] == candidates[i]) i++; dfs(i + 1, combination, combinations, candidates, sum, target); } public List combinationSum2(int[] candidates, int target) { List combinations = new ArrayList(); Arrays.sort(candidates); dfs(0, new ArrayList(), combinations, candidates, 0, target); return combinations; } }
@symbol7672 жыл бұрын
I really logically struggle to understand the time complexity of this problem and why its 2N. We can include 10, but if not we could skip it in our FOR LOOP, but if we skip it that doesn't mean we are calling the recursion on nothing. We just go to the next number, 1 in our case, then try that, lets assume 1 also didn't work, then we go to 2, then 7, etc. Super confusing...
@smitaagarwal8819 Жыл бұрын
can be solved just by adding one condition in combination sum I problem -- def combinationSum2(self, candidates: List[int], target: int) -> List[List[int]]: res = [] candidates.sort() def dfs(i, cur, total): if total == target: res.append(cur.copy()) return if i >= len(candidates) or total > target: return cur.append(candidates[i]) dfs(i+1, cur, total+candidates[i]) cur.pop() #to avoid duplicate while (i+1 < len(candidates) and candidates[i] == candidates[i+1]): i = i+1 dfs(i+1, cur, total) dfs(0, [], 0) return res
@MarcoPolo-n3u7 күн бұрын
Happy Daily
@lucaslu17313 жыл бұрын
I tried your solution with test case ([10,1,2,7,6,1,5], 8), and the result is missing [1, 1, 6]. Somehow it also skips adding the second number 1 there even thou it's valid
@greatred25582 жыл бұрын
Exactly
@prempeacefulchannel3 жыл бұрын
I found out your channel by searching dp problems. Great explanations man! Subscribed instantly
@KartikeyTT2 ай бұрын
Guys just use the same code as that of subset 2 and just add extra base condtions where you exceed the sum and where you find the sum
@shrimpo64162 жыл бұрын
man, thank you for the explanation! clean & neet
@nithinrao7191 Жыл бұрын
What was also a bit confusing was that the decision tree that was drawn has 2 branches whereas the code has N branches staring from the root, is that right or am I missing something here? Wouldn't the runtime of this be more like N^N as the branching factor is N and not 2?
@melissac4872 Жыл бұрын
Nah it should be 2^N
@reggiehurley1479 Жыл бұрын
im pretty sure he coded up the wrong decision tree. Other commentors ahve provided the binary tree solution implementation though
@amangaur42312 жыл бұрын
How neatly u explain man! Awesome 😎
@tejasnakhate2 жыл бұрын
What will be the time complexity of this approach? I feel it will be 2^N where n is the number of unique elements in the list. What do you think?
@MrLeyt11255 ай бұрын
I dont get it. We have two ways: use number in combination or skip it. With backtrack(cur, i+1, target - candidates[i]) we use current number in combination. But in which part of code we dont use that number and skip it? Please explain
@codingstation77413 жыл бұрын
Thanks neetcode, really like your videos!
@chillegaming82503 жыл бұрын
So simple.. thank you!
@WhoMePrime2 жыл бұрын
I prefer the 0/1 knapsack DP aproach to this problem, but pretty sure the time complexity is 2^N * T, where T is the target since you have to traverse the dp array for each number. Hope this helps those who aren't great at backtracking, like myself... def combinationSum2(self, candidates, target): candidates.sort() dp = [set() for _ in range(target+1)] dp[0].add(()) for num in candidates: for i in range(target, num-1, -1): for subSet in dp[i-num]: subSet += (num,) dp[i].add(subSet) return dp[-1]
@spacetoast7783 Жыл бұрын
Why can't this be implemented as a binary DFS/backtrack? Each branch would decide whether or not a certain-indexed candidate is included. For reasons I don't understand, I can only get this to work with an n-ary implementation. In other words, why is the binary decison whether we include any 1 instead of any particular instance of 1?
@linshen4658 Жыл бұрын
Thanks a lot for the video. I love it. I just got a question: isn't the tree to illustrate your code should be like, first level: [], second-level [1] [1] [2]...[7][10], and then, the children of first left child of second-level be [1][2]...[7][10] ? Note that the for loop starts with all the elements in the range, instead of a take or not take binary tree.
@romo119 Жыл бұрын
Why isn't the time complexity n*2^n ? You have to make a copy of each combination to add to the return array
@difengchen6431 Жыл бұрын
I think this problem allows us to have the duplicate numbers if they are on different indices.
@raj_kundalia Жыл бұрын
thanks for the explanation!
@HeinekenLasse2 жыл бұрын
Great solution. I couldn't figure out how to get rid of the duplicates by myself. I tried everything, sets, hashMaps, even using the return of the backtrack function to eliminate the used nums from candidates. Nothing worked =/
@mycityofsky2 жыл бұрын
Great explanation, thanks!
@prathamkesarkar2 жыл бұрын
Wow the only missing thing for me is i > start this was the reason my answer was not getting accepted
@fancyAlex19933 ай бұрын
Can we not use a hashmap ? Honestly I found the explanation very confusing
@dimplekhuman9147Ай бұрын
Can't we just take set of input list and reuse combination sum I solution?
@andrewtran979 Жыл бұрын
If you continue to extend the tree you made in your drawing explanation, won't you find duplicates?
@bensonjin3472 жыл бұрын
Why do you do target - candidates[i] as opposed to storing a total and adding candidates[i] like for combination sum I?
@finchshi4342 Жыл бұрын
Why is this time we are subtracting value from target, not summing up values to reach target?
@reggiehurley1479 Жыл бұрын
im pretty sure the code is different from the decision tree he showed lol. The decision tree he showed is a binary tree but his code isn't.
@AryanSingh-eq2jv2 ай бұрын
u can also break since they are sorted on bigger value
@zarifmahfuz96 Жыл бұрын
Why is the time complexity of this solution not O(n * 2^n) like the Subsets II problem?
@MS-ib8xu Жыл бұрын
Instead of initializing prev to -1, why don't you initialize it to None? Can python compare a None and an int?
@Aminbenabdelhafidh7 ай бұрын
when I tried your solution code it didn't work so I replaced 'for i in range(len(candidates))' with 'for j in range(i, len(candidates))' and it did work. Can you guys explain why is that?
@arpitkumar17812 жыл бұрын
class Solution: def combinationSum2(self, candidates: List[int], target: int) -> List[List[int]]: candidates.sort() result = [] curr = [] def backtrack(start, target): #base case 1 if target == 0: result.append(curr.copy()) return #base case 2 if target < 0: return for i in range(start, len(candidates)): #handling duplicate elements if i > start and candidates[i] == candidates[i - 1]: continue curr.append(candidates[i]) backtrack(i + 1, target - candidates[i]) curr.pop() if target
@arpitkumar17812 жыл бұрын
this way we can skip unnecessary cases
@xujia1001 Жыл бұрын
This is really good stuff. Thanks for sharing!
@amanbhatia74428 ай бұрын
Is there a reason why you deviated from the pattern used in Combination Sum I ???
@impostorX Жыл бұрын
Why can't we use this one instead at line 14-15? if i + 1 < len(candidates) and candidates[i] == candidates[i+1]: continue As we did in subset problem with duplicates?
@monicawang8447Ай бұрын
I have the same question! Has anyone figured it out?
@orangethemeow2 жыл бұрын
Just realized that the technique here is the same as #90
@IAmIndraTheGod2 жыл бұрын
time complexity ?
@ianokay8 ай бұрын
You should remake this video. It's hard to follow for the first time when it's full of incorrect logic and then only later cleaned up right before ending
@KartikeyTT2 ай бұрын
the code doesnt match the explanation. In the explanation you were making 2 decisions....but in the code the number of decisions is decided b the loop
@BilliamSilliam6 күн бұрын
How do you print it….
@MS-vx4vd Жыл бұрын
God Im so terrible at this rip
@gyan26642 жыл бұрын
class Solution(): def dfs(self, arr, index, target, isIncluded, path=[]): if target == 0: self.result.append(path) return if index < len(arr) and target < arr[index]: ## this condition speeds up the programme a lot as lot of negative cases are coming return self.dfs(arr, index+1, target, False, path) if index == len(arr): return else: self.dfs(arr, index+1, target, False, path) if index > 0 and arr[index-1] == arr[index] and not isIncluded: return self.dfs(arr, index+1, target-arr[index], True, path+[arr[index]]) def combinationSum2(self, arr, target): self.result = [] self.dfs(sorted(arr), 0, target, False) return self.result
@saiteja88702 жыл бұрын
Bounded knapsack
@kinnikuchu2 жыл бұрын
Why are you calling target - candidates[i] at the recursive function? Word of advice, you should run a step by step demonstration of your code and make your explanation without rushing, as it feels you just want to finish up the video as quickly as possible.
@ranjitkoragoankar Жыл бұрын
5:17
@chanduiit422 жыл бұрын
Doesn't the time complexity become O(n!) because we choose n elements in the first choice, n-1 elements for the second layer and so on? Can you clarify this please..
@derilraju2106 Жыл бұрын
each element has a choice of whether being selected or not thus 2^n?
@abhicasm92372 жыл бұрын
Am I really that dumb?
@mido52192 жыл бұрын
no you're not backtracking can be annoying sometimes 😂😂
@ShailPM3 ай бұрын
Dont look at this. There is an easier answer on leetcode
@TanishBansal-ss2ou3 ай бұрын
based of combination sum 1 and subset 2 : class Solution: def combinationSum2(self, candidates: List[int], target: int) -> List[List[int]]: res = [] candidates.sort() def dfs(i,cur,total): if total == target: res.append(cur.copy()) return if i >= len(candidates) or total > target : return cur.append(candidates[i]) dfs(i+1, cur, total + candidates[i]) cur.pop() while i + 1 < len(candidates) and candidates[i] == candidates[i+1]: i += 1 dfs(i + 1, cur, total) dfs(0,[],0) return res