Man, you single handedly upped my backtracking game! Your format is so easy to follow and I can actually solve more backtracking questions with this line of thought - you brought in a LOT of structure in how to think/reason a backtracking problem. I used to RUN AWAY when I'd see a backtracking problem, now I can get thru mediums and halfway thru hards but hey, I'll get there! Thank you so much!!
The only solution on TH-cam that made sense (to me), because my code was exactly the same, I was only missing the while loop and ending up with a TLE. And now I know why. Thanks a ton, Nav!
I mostly pause your videos at the Drawing stage and go and solve it myself. That is what I am trying to learn from your channel : how to visualise the sequence of steps reqd for solving the problem
I'm surprised you don't need to make a copy of the "cur" because further down into the recursion I would expect that it would be problematic to change the list
We can significantly improve the time complexity by placing a conditional check before the while loop. Since we have sorted the array we know that if our current sum plus the current value we are viewing exceeds the target, then there is no need to search further right, since all values will exceed target by an even greater margin. We can check this and return if True. For example: candidates = [1,1,3,4,5,6,7,8,9], target = 3 If we have [1,1] in our combination, then add 3 and see it that [1,1,3] exceeds 3 (ie. 5 > 3) then there is no need to also check that [1,1,4], [1,1,5], [1,1,6] etc are also in excess of the target Edit, just saw a different comment reflecting this, I'll leave this up in case it helps someone
For someone still struggling to understand why the loop is required, here is my take on this 💡The core idea 💡 If there are repeated elements you include elements from prefix (of group of same elements) and explore next but once you exclude the element you exclude all element of same values, because from here onwards you don't need to include any values, if it was required we would have already explored this case previously where choose the value from prefix.
alternatively, don't append the value and instead add an array with the next value, and you don't have to copy or pop either def combinationSum2(self, candidates: List[int], target: int) -> List[List[int]]: output = [] candidates.sort() def backtrack(i=0, arr=[], total=0): if total == target: output.append(arr) return if i >= len(candidates) or total > target: return # add case backtrack(i + 1, arr + [candidates[i]], total + candidates[i]) # don't add case while i + 1 < len(candidates) and candidates[i] == candidates[i + 1]: i += 1 backtrack(i + 1, arr, total) backtrack() return output
DSA is sadly so hard. Difficult to break into MAANG companies. Create a strong portfolio in dev skills like full-stack, cloud, and now you're open for other roles. DSA is truly depressing.
Have you solved Combination Sum and 3Sum before? If not I would make sure you understand those first. Without the loop you will get duplicate combinations. I would highly recommend drawing the decision tree yourself, that's the only way to learn. Relying on explanations will only get you so far.
We need while loop to eliminate duplicate result. else it will give same result. ie. 1,1,1,3,4,5, target = 8, without while loop you will get 1,3,4 then again 1,3,4 and then again 1,3,4 but using while you ignore other 2 duplicate 1s and only process 1 once at given branch level so it would be just 1,3,4
@@NeetCodeIO It works! I missed the extra variable part at the first attempt. def combinationSum2(self, candidates: List[int], target: int) -> List[List[int]]: candidates.sort() res = [] def helper(tmp, i, tar): if tar == 0: res.append(tmp.copy()) return if i == len(candidates) or tar < 0: return j = i while i+1 < len(candidates) and candidates[i] == candidates[i+1]: i += 1 helper(tmp, i+1, tar) tmp.append(candidates[i]) helper(tmp, j+1, tar-candidates[j]) tmp.pop() helper([], 0, target) return res
@@NeetCodeIO I have a general question. Could you share how did you "deep-understand" the leetcode skills? Like how we can study and check if we are ready and learned LC deep enough. Personally, I have a problem that I could understand a LC problem after watching your videos and understanding the logic. However, when I tried to do the other problems in same category, I feel like I am not truly understanding them and not learned deep enough.
Actually Confused between cur and total, both are passing as arguments,cur changing and total remains same, after some visualisation, finally what i understand is cur is poining in memory but not total. Thanks@@NeetCodeIO , got it.
@@NeetCodeIO what i meant is if the total is greater than the target we can skip the while loop so the recursion wont happen something like below if (total + candidates[index]) < target: // do while loop and recursion stuff
@@serhiikopytchuk yeah i agree! But what i meant is from the above eg if we know that 1,1,2,5 is greater than the target! We dont need to again dfs for 1,1,2,7 or 1,1,2,8 or 1,1,2,10 etc
You glossed over the most important part - with the way you explained it, [1,1,6] should never be possible because you're only ever recurring over unique elements. Why is the second 1 in [1,1,6] included? For an example where you have [1,1,....,6,6...] and target=8, why won't you end up with [1,1,6] twice?
Oh oops you did mention it - it's because our two branches are: A) exclude ALL occurrences of the element from this point onwards(while loop till we find a next unique element in the sorted array), this happens even IF the element is in our path B) include the element, even if it's in our path
class Solution: def combinationSum2(self, candidates: List[int], target: int) -> List[List[int]]: curset = [] subset = [] candidates.sort() def helper(i,nums,curset,subset): if i >= len(nums): return
if sum(curset) > target: return
if sum(curset) == target: subset.append(curset.copy()) return
curset.append(nums[i]) helper(i+1,nums,curset,subset) curset.pop() while i+1 < len(nums) and nums[i] == nums[i+1]: i = i + 1 helper(i+1,nums,curset,subset) return subset
return helper(0,candidates,curset,subset)
This code is very similar, but only gives me solution [[1,2,2]] for the use case candidates = [2,5,2,1,2], target = 5. Can someone please explain ?
You must first check if the current sum is equal to target before checking if i >= len(candidates) since i will be greater than length for the last element case (here when when you add 5 to curset, i will be 6)
I believe there is a mistake here. You pointed out that we can't the first approach where we take each number and then combine with others because it will cause duplicate. That's incorrect because question is pointing out that numbers are unique. This means that when you move to next index, you won't see the same number again. Therefore, you can take that approach. Start from an index and go all the way forward and backtrack. for(var i=index; i < input.Length; i++) { var value = input[i]; list.Add(value); FindTarget(index, target-value, list, input); list.RemoveAt(list.Count-1);
FindTarget(index+1, target, list, input); } This should work fine.
NeetCode 150 - neetcode.io/practice
Combination Sum Part 1 - th-cam.com/video/GBKI9VSKdGg/w-d-xo.html
Man, you single handedly upped my backtracking game! Your format is so easy to follow and I can actually solve more backtracking questions with this line of thought - you brought in a LOT of structure in how to think/reason a backtracking problem.
I used to RUN AWAY when I'd see a backtracking problem, now I can get thru mediums and halfway thru hards but hey, I'll get there! Thank you so much!!
Backtracking has always been a headache for me.
The trick to this is similar to Subsets II. Solving and understanding Subsets II will make solving this problem easier
That's why they're in order on the roadmap 😉
The only solution on TH-cam that made sense (to me), because my code was exactly the same, I was only missing the while loop and ending up with a TLE. And now I know why. Thanks a ton, Nav!
same happened with me
Your explanations are even clearer now👌
I mostly pause your videos at the Drawing stage and go and solve it myself. That is what I am trying to learn from your channel : how to visualise the sequence of steps reqd for solving the problem
I'm surprised you don't need to make a copy of the "cur" because further down into the recursion I would expect that it would be problematic to change the list
We can significantly improve the time complexity by placing a conditional check before the while loop.
Since we have sorted the array we know that if our current sum plus the current value we are viewing exceeds the target, then there is no need to search further right, since all values will exceed target by an even greater margin. We can check this and return if True.
For example: candidates = [1,1,3,4,5,6,7,8,9], target = 3
If we have [1,1] in our combination, then add 3 and see it that [1,1,3] exceeds 3 (ie. 5 > 3) then there is no need to also check that [1,1,4], [1,1,5], [1,1,6] etc are also in excess of the target
Edit, just saw a different comment reflecting this, I'll leave this up in case it helps someone
Thanks for going over both runtime and space complexity in your recent videos :)
This problem is 99% similar to subsets 2 problem
This is so much easier to understand
For someone still struggling to understand why the loop is required, here is my take on this
💡The core idea 💡
If there are repeated elements you include elements from prefix (of group of same elements) and explore next but once you exclude the element you exclude all element of same values, because from here onwards you don't need to include any values, if it was required we would have already explored this case previously where choose the value from prefix.
Beautifully explained. Thank you
The solution was simpler than expected
This helped me a lot.
Nice!!🎉🎉
wondering if this could be done iteratively instead of using recursion?
alternatively, don't append the value and instead add an array with the next value, and you don't have to copy or pop either
def combinationSum2(self, candidates: List[int], target: int) -> List[List[int]]:
output = []
candidates.sort()
def backtrack(i=0, arr=[], total=0):
if total == target:
output.append(arr)
return
if i >= len(candidates) or total > target:
return
# add case
backtrack(i + 1, arr + [candidates[i]], total + candidates[i])
# don't add case
while i + 1 < len(candidates) and candidates[i] == candidates[i + 1]:
i += 1
backtrack(i + 1, arr, total)
backtrack()
return output
The goat
DSA is sadly so hard. Difficult to break into MAANG companies.
Create a strong portfolio in dev skills like full-stack, cloud, and now you're open for other roles.
DSA is truly depressing.
If target was a large number (>100), will backtracking with array of length 100 give TLE (or stack overflow)
combination sumll=cobination subl + subsetll
I am still not getting the while loop part. Why it's needed ? Can anyone explain ?
Have you solved Combination Sum and 3Sum before?
If not I would make sure you understand those first.
Without the loop you will get duplicate combinations. I would highly recommend drawing the decision tree yourself, that's the only way to learn.
Relying on explanations will only get you so far.
We need while loop to eliminate duplicate result. else it will give same result. ie. 1,1,1,3,4,5, target = 8, without while loop you will get 1,3,4 then again 1,3,4 and then again 1,3,4 but using while you ignore other 2 duplicate 1s and only process 1 once at given branch level so it would be just 1,3,4
applied the same but saying time limit exceded
Wondering if we can write Skip dfs first then the Including dfs? and how would it look?
you could but you would prob need another variable to keep track of the original index
@@NeetCodeIO thanks for the tip. Let me try it :)
@@NeetCodeIO
It works! I missed the extra variable part at the first attempt.
def combinationSum2(self, candidates: List[int], target: int) -> List[List[int]]:
candidates.sort()
res = []
def helper(tmp, i, tar):
if tar == 0:
res.append(tmp.copy())
return
if i == len(candidates) or tar < 0:
return
j = i
while i+1 < len(candidates) and candidates[i] == candidates[i+1]:
i += 1
helper(tmp, i+1, tar)
tmp.append(candidates[i])
helper(tmp, j+1, tar-candidates[j])
tmp.pop()
helper([], 0, target)
return res
@@NeetCodeIO I have a general question. Could you share how did you "deep-understand" the leetcode skills? Like how we can study and check if we are ready and learned LC deep enough.
Personally, I have a problem that I could understand a LC problem after watching your videos and understanding the logic. However, when I tried to do the other problems in same category, I feel like I am not truly understanding them and not learned deep enough.
tough one
Upload today's(14 august) daily problem please!
You have already posted this video already in your other channel
@NeetCodeIO or anyone please help
how total is decreasing after pop?
We never modify total, we pass in the sum as the argument in the skip case. I feel like it's pretty straight forward if you read the code
Actually Confused between cur and total, both are passing as arguments,cur changing and total remains same, after some visualisation, finally what i understand is cur is poining in memory but not total.
Thanks@@NeetCodeIO , got it.
can someone explain for me deeper why i cant use dynamic programing ?
You can but it won't improve the time complexity because you still have to generate the solution set which would be n*2^n in worst case
because there is nothing repeating. every operation is unique
we can skip the while loop, if the total is greater then the target, its unnecessary to go to recursion in this case
What's the solution without the loop?
@@NeetCodeIO what i meant is if the total is greater than the target we can skip the while loop so the recursion wont happen something like below
if (total + candidates[index]) < target:
// do while loop and recursion stuff
@@Manikandan-li4cd We just do same thing into the dfs function. So there no need to repeat
@@serhiikopytchuk yeah i agree! But what i meant is from the above eg if we know that 1,1,2,5 is greater than the target! We dont need to again dfs for 1,1,2,7 or 1,1,2,8 or 1,1,2,10 etc
DRY: don't repeat yourself principle, we are checking at top if sum is greater we are returning, why to write same thing again below while loop.
You glossed over the most important part - with the way you explained it, [1,1,6] should never be possible because you're only ever recurring over unique elements. Why is the second 1 in [1,1,6] included?
For an example where you have [1,1,....,6,6...] and target=8, why won't you end up with [1,1,6] twice?
Oh oops you did mention it - it's because our two branches are:
A) exclude ALL occurrences of the element from this point onwards(while loop till we find a next unique element in the sorted array), this happens even IF the element is in our path
B) include the element, even if it's in our path
class Solution:
def combinationSum2(self, candidates: List[int], target: int) -> List[List[int]]:
curset = []
subset = []
candidates.sort()
def helper(i,nums,curset,subset):
if i >= len(nums):
return
if sum(curset) > target:
return
if sum(curset) == target:
subset.append(curset.copy())
return
curset.append(nums[i])
helper(i+1,nums,curset,subset)
curset.pop()
while i+1 < len(nums) and nums[i] == nums[i+1]:
i = i + 1
helper(i+1,nums,curset,subset)
return subset
return helper(0,candidates,curset,subset)
This code is very similar, but only gives me solution [[1,2,2]] for the use case candidates = [2,5,2,1,2], target = 5. Can someone please explain ?
You must first check if the current sum is equal to target before checking if i >= len(candidates) since i will be greater than length for the last element case (here when when you add 5 to curset, i will be 6)
I believe there is a mistake here. You pointed out that we can't the first approach where we take each number and then combine with others because it will cause duplicate. That's incorrect because question is pointing out that numbers are unique. This means that when you move to next index, you won't see the same number again. Therefore, you can take that approach. Start from an index and go all the way forward and backtrack.
for(var i=index; i < input.Length; i++) {
var value = input[i];
list.Add(value);
FindTarget(index, target-value, list, input);
list.RemoveAt(list.Count-1);
FindTarget(index+1, target, list, input);
}
This should work fine.
Actually the question does not say numbers are unique, thats combination sum i
Such a confusing problem..
I can not solve backtracking problems on my own. Using recursion is hard for me.