Most backtracking problems on leetcode follow this dfs pattern. A lot of them also have this loop inside structure as well. It's pretty easy once you get the gist of it.
This is a genius solution! Once we exhaust a specific number in the candidates (either by going over or hitting the target), we pop back up to the previous call using a new number (in this case it'd be a higher number since the list is sorted and distinct). So we're basically avoiding any previous combinations and building a tree from bottom up, from left to right. Amazing diagram, you're the best NeetCode.
i think the most challenging part of this problem was in knowing how to "traverse" the elements. The base cases are pretty simple (tbh, most recursive graph/tree problems are, but here it's even more straightforward), but it wasn't apparent to me how you'd keep track of repeated elements. In hindsight, this is done by calling dfs at the same index (but making sure to add/remove the element accordingly) and is pretty obvious once you know it.
Bro , you should check out striver, he's great at explaining questions and is one of the best with dsa knowledge and competitive programming. Channel - TUF
Great explanation. Much better than AlgoMonster. I didn't understand why we could exclude candidates until you explained how each node splits into including or excluding a candidate.
This is very similar to a problem that I’m still looking for a dynamic programming solution for… I was never able to figure it out. Neetcode, you’re my only hope!
if you read the solution in leetcode, it is just a dfs tree, except it sorts the candidates, then in the loop, to avoid duplication, you just need to check if the next element is less or larger then the last element in the current combination.
@@liliwen8831 i think the trick for all these kinds of problems is that it is almost always dfs on tree. the number of branches correspond to the number of times you need to recurse. the reason for branching is represented in the call. any time you need to make a decision in a recursion problem, that is a branch on your tree, and you need to exhaust it with dfs.
this problem is extremely simple. You just need to know how to solve backtracking problems and specifically how to generate combinations (which is eliminate duplicate combinations)
If the cur.append and cur.pop is confusing, you could just add to cur within the recursive call instead: def dfs(i, curList, total): if total == target: res.append(curList) return if total > target or i >= len(candidates): return
dfs(i, curList + [candidates[i]], total + candidates[i]) dfs(i + 1, curList, total) 2 fewer lines of code and you don't have to pop from cur after the first recursive call.
the issue with this is you are generating a new list every time you call the function and they need to be cleaned up by the GC. Using the same list with the pop function is memory efficient.
If you sort inputs. Problem becomes easy. First populate stack: For every item at index i > list[-1] not in list. Pop n and put it in a list if sum list < target, then add list to stack. Then pop a list from the stack and repeat the above continuously for every item in the stack. If the sum of the list == target, add to result. If > target, remove from stack. If < target, add list + [i] to stack. If you want to save more space you dont need a memo if you take a list of indexes, they will be the same as the memo. This is iterative and should get every possibility without duplication.
space complexity is O(target val / smallest val in candidates) b/c max depth of the tree is when it keeps adding the smallest element to the combination until it hits or exceeds target. time: O(number of candidates^max depth)
came up with similar solution, with only 2 parameters for the inner function: res = [] def backtrack(i, total): if i == len(candidates) or sum(total) > target: return if sum(total) == target: res.append(total.copy()) return backtrack(i, total + [candidates[i]]) backtrack(i + 1, total) backtrack(0, []) return res
Man, this took me forever to wrap my head around. Either I am too stupid for my desired career path as a non-CS major or this is too difficult for a medium problem.
I found it very interesting to implement this problem with iterative solutions. It translates quite straightforwardly (though it is finicky) to storing the working information on a stack, and then iterating through and processing each node on the stack instead. It taught me a lot about how functional recursion can relate to iterative recursion. The key is to store all the relevant information on a stack, basically copying how it would be implemented with a function call (ie. function call needs index argument, sum of elements, set of elements), then popping that information off the stack while you process it. I had a working vector of vectors - each vector within it contained the working set up to that point, then two more variables right at the end containing the current index, and the sum up to that point. Each loop, pop a vector from the stack, process it, and add its children to the stack if its valid (or add the results if they match the requirements). Eventually the stack is empty and you return the results. The other fun part is it becomes extremely straightforward to convert the iterative implementation to a BFS search instead (checking solutions at the top of the tree instead), by simply converting the stack (I implemented it with std::vector) to a queue (eg. std::deque), and pop the working information from the front instead of the back.
class Solution: def combinationSum(self, candidates: List[int], target: int) -> List[List[int]]: res=[] n=len(candidates) def comb(arr,ind): if target < sum(arr): return if target==sum(arr): res.append(arr.copy()) return for i in range(ind,n): arr.append(candidates[i]) comb(arr,i) arr.pop() return comb([],0) return res Finally, I got an idea of how to do backtracking after some 20 backtracking problems from your channel. I just want to share the code I wrote 😇
Here's my implementation: class Solution(object): def combinationSum(self, candidates, target): """ :type candidates: List[int] :type target: int :rtype: List[List[int]] """ ans = []
def dfs(i, curr_sum, curr_lst): if curr_sum == target: ans.append(curr_lst[:]) if curr_sum >= target or i >= len(candidates): return for j in range(i, len(candidates)): curr_lst.append(candidates[j]) dfs(j, curr_sum + candidates[j], curr_lst) curr_lst.pop()
Hey Edward Thanks for the solution . can you explain me what is the reason behind adding [:] in "ans.append[:]" , i try executing the code without "[:]" and its return the empty list. And its working with [:] . From my knowledge they are basically doing the same thing i guess
@@ritikdwivedi5983 The [:] is another shortcut to create a copy of the curr_lst and append the curr_lst inside the ans(answer) array. The reason you want to create the copy and insert into the array is because the curr_lst is constantly changing with values being added and removed as you go through the recursion. I highly recommend debugging and you'll see what I and Neetode meant and why it's vital to include the [:] The empty list is possibly from the curr_lst.pop(), but that's just a guess lol
Very good approach that outlines a classic use of DFS and backtracking. I solved the problem differently, using a recursive approach, but the issue was the time performance of my algorithm which ended up suffering (bottom 5th percentile!). Thanks for your solution.
Here is the Java code for reference:- public List combinationSum(int[] candidates, int target) { Listl=new ArrayList(); backtrack(l,candidates,target,0,new ArrayList(),0); return l; } public void backtrack( Listl, int[] arr, int target, int sum, Listrow, int i) { if(sum==target){ l.add(new ArrayList(row)); return; } if(i>=arr.length || sum>target){ return; } row.add(arr[i]); backtrack(l,arr,target,sum+arr[i],row,i);
You can also use a for loop, rather than calling out both conditions explicitly. def combinationSum(self, candidates: List[int], target: int) -> List[List[int]]: res = [] def backtrack(i, cur): cursum = sum(cur) if cursum == target: res.append(cur.copy()) return if i >= len(candidates) or cursum > target: return False for j in range(i, len(candidates)): backtrack(j, cur + [candidates[j]]) backtrack(0, []) return res
After watching previous video, I successfully solved this on my own. Upon reviewing your explanation, I realized that we arrived at the same solution. So happy that i improved, ty
@@jyotindersingh3458 This is my general understanding of the time complexity (based on Leetcode solution of O(N^T/m)). The decision tree is an N-ary tree, which means that each node can have up to N nodes (ie. in the example, N = 4 because length of candidates is 4). T/m determines max depth of tree, where m is min val of candidates, and T is target. Worst case would be if m = 1, then T/m = T, so a depth of 7. To simplify, O(N^T) worst case makes sense to me.
Great explanation. I think the time complexity is 2 ^ (t/2) because the smallest number is actually 2 so the length of the smallest combination will be t/2 for example if t is 8 the smallest combo is 2,2,2,2 which is 8/2.
Actually the tree suggested, is a very nice solution if you sort the array first. Then the most left value can only use values from it's right (including itself) While the farther right you are in the tree / sorted array, you cannot use those values. Thus you won't create duplicates. And you'll make less calculations then a full on backtrack. So you can also take unique values only from candidates, and sort them out.
4:40 was Gold. Thank you. ''' how many ways can I sum up to target given a sequence of candidates ''' answer = [] path = [] def dfs(target, nums): if target < 0: return if target == 0: answer.append(path.copy()) return
for idx, num in enumerate(nums): path.append(num) dfs(target - num, nums[idx:]) #4:40 we dont recurse on the 2. ;) path.pop() dfs(target, candidates) return answer
Some people are really great at teaching. You are one of them ,I have been pulling my hair since last night. I was facing the issue where the solutions were repeating and wasn't sure how to handle it . Thanks a lot ❤
this problem is like Coin Change 2 while the exact combinations need to be reserved, so a dp[target+1] list of lists instead of integers could be used to implement that track. The combinations of all 0~target have to be saved, but it won't need the recursion stack.
We could optimize this solution by sorting nums and stopping recursion if prev element in sorted array itself didn't add up to result For this example candidates = [2,3,6,7], target = 7 The usual dfs solution will trace in the below way 2 - 2 - 2 - 2(8 > target) so return 2 - 2 - 2 - 3 2 - 2 - 2 - 6 2 - 2 - 2 - 7 After completing the above pattern only it will move one level up 2 - 2 - 3(7 == target) if you notice in the first pattern, already adding up index - 0 which is 2 makes the target bigger Why do we need to go down on the sorted array by trying the next larger nos? Thus breaking that level will save considerable time Complete Code: def combinationSum(self, nums: List[int], target: int) -> List[List[int]]: n = len(nums) nums.sort() results = [] subset = [] def dfs(target, index): if target == 0: results.append(subset.copy()) return for i in range(index, n): new_target = target - nums[i] if new_target >= 0: subset.append(nums[i]) dfs(new_target, i) subset.pop() else: return dfs(target, 0) return results Leetcode post link: leetcode.com/problems/combination-sum/discuss/2606968/Python-Beats-99.5-one-Tweak-from-usual-dfs-solution
thx dear But I have two questions first: what if we start with 0 I think the recursion will not get out of this condition total will not = the target ,i < length of candidates and total < target what is the explanation here the second what if we found a list that match the target and after that we reach a zero it should make also a list but the code will pop the last element and move to the next index for example 2 +2 =4 and 2+2+0=4 but the code cur.pop() dfs(i +1 ,cur ,total)
solution with sorting class Solution: def combinationSum(self, candidates: List[int], target: int) -> List[List[int]]: dp = {i : [] for i in range(target + 1)} for candidate in candidates: dp[candidate] = [[candidate]] for total in range(1,target + 1): for candidate in candidates: for a in dp.get(total - candidate,[]): new = [candidate] + a new.sort() if new not in dp[total]: dp[total].append(new) return dp[target]
Shouldn't the time compelxity be O(t*2^(nt))? Yes depth is "t", but we start tree from each elements in candidates. Even in the tree you drew, if you don' take a number, you actually start a new tree with that number. So, for elements [1, 2, 3] and target 4, shouldn't the actual time complexity be: Starting with 1: 2^4 Starting with 2: 2^4 Starting with 3: 2^4 So, 2^4*2^4*2^4 = 2^(3*4) Fianlly, in each call we are adding cur array to res. Which has worst case complexity of "t". So, is the final complexity: O(t*2^(n*t))?
can we just rearrange the last 4 lines to avoid pop altogether. Basically mirror the decision tree class Solution: def combinationSum(self, candidates: List[int], target: int) -> List[List[int]]: res = [] def dfs(i, cur, total): if total == target: res.append(cur.copy()) return if i >= len(candidates) or total > target: return dfs(i + 1, cur, total) cur.append(candidates[i]) dfs(i, cur, total + candidates[i])
Slight modification where we don't have to add/pop from the list manually. Also, where we use python sugar to copy the list: class Solution: def combinationSum(self, candidates: List[int], target: int) -> List[List[int]]: res = [] def dfs(i, cur, total): # base case 1), we hit a valid target if total == target: res.append(cur[:]) # make sure to pass a copy return # base case 2), we are out of bounds or exceeded the target if i >= len(candidates) or total > target: return # need to check both branches: repeating the current candidate, and excluding it dfs(i, cur + [candidates[i]], total + candidates[i]) dfs(i + 1, cur, total) # call it with an empty total and empty initial list dfs(0, [], 0) return res
I like copying the list here better but this is probably the only time where I would actually rather pop the candidate manually, so that why I can remember what's actually going on in the code.
a cleaner solution is class Solution: def combinationSum(self, candidates: List[int], target: int) -> List[List[int]]: output = [] def find(options: list[int], total: int, start: int): # base case if start == len(candidates) or total > target: return for i in range(start, len(candidates)): item = candidates[i] if total + item == target: output.append(options + [item]) elif total + item < target: find(options + [item], total + item, i) find([], 0, 0) return output thanks for your work
I think he had to because, dfs is called 2 times recursively , once with i val and other without i val, and without passing , how cur can have 2 values at the same time. correct me if I am wrong
What doesn't make sense to me in this explanation is why go over the cases where you wouldn't add anything to the array, I think spliting each time between adding and not adding an element is faster and maybe a bit easier to understand for some. I'll leave my solution here if it helps anyone. class Solution { public: vector combinationSum(vector& candidates, int target) { vector result; vector subset; DFS(result, subset, candidates, target, 0, 0); return result; } private: void DFS(vector& result, vector& subset, const vector& candidates, int target, int sum, int index) { if (sum >= target) { if(sum == target) { result.push_back(subset); } return; } for(int i = index; i < candidates.size(); i++) { subset.push_back(candidates[i]); DFS(result, subset, candidates, target, sum + candidates[i], i); subset.pop_back(); } } };
I really like all your explanations ,although I code cpp, your explanations with drawings does make a beneficial help.(even for an Asian from tw who speak poor English
Nothing makes me feel more stupid than generating combinations using backtracking. I can do backtracking on matrix without a problem, but as soon as you have combinations or permutations I just get lost even drawing the tree. Like, when we got to [2, 2, 2], I get that adding another two going down the left subtree [2, 2, 2, 2] you get an 8 which is over the target and that's why that branch should stop, but then why didn't we keep going down the right subtree infinitely?
My understanding is that since we keep incrementing i, the pointer for our candidates list, the pointer goes out of bounds, so the the dfs function returns (that was one of our base cases)
I was able to make it work with the first tree, but the time complexity is bad. class Solution: def combinationSum(self, candidates: List[int], target: int) -> List[List[int]]: res = set() temp = [] def dfs(total): if total==target: res.add(tuple(sorted(temp[:]))) return if total>target: return for c in candidates: temp.append(c) dfs(total+c) temp.pop() dfs(0) return [list(t) for t in res]
why won't it work when I call dfs in the opposite order: dfs(i + 1, cur, total) cur.append(candidates[i]) dfs(i, cur, total + candidates[i]) I thought this was cleaner but it gives wrong answer, why is that?
if you sort the candidates in descending order it's simpler sols = [] candidates.sort(reverse=True) dfs(candidates, target, ()) return sols def dfs(candidates, target, prefix): if candidates: for i, c in enumerate(candidates): if c > target: # no way to reach the target if all candidates positive continue elif c == target: # found a solution, no more possible if all candidates positive sols.append(prefix + (c,)) else: dfs(candidates[i:], target-c, prefix + (c,)) # find all solutions starting with c
Why can't we use dfs for not including the element first, then appending it and then dfs for using it? Doing so gives me very strange and wrong outputs. Eg- dfs(ctr + 1, nums, curr, total, target) curr.append(nums[ctr]) dfs(ctr, nums, curr, total + nums[ctr], target) gives [[7],[7,6,7,6,3,7,6,3,7,6,3,2,7,6,3,7,6,3,2,7,6,3]] for target == 6 and candidates == [2,3,6,7] whereas using curr.append(nums[ctr]) dfs(ctr, nums, curr, total + nums[ctr], target) curr.pop() dfs(ctr + 1, nums, curr, total, target) gives [[2,2,3],[7]] as expected?
This "append" and then "pop" is a little bit confusing. For me is more intuitive - 1st launch recursive, then append, then launch recursive again. No pops. Don't forget to copy cur on every recursion call.
I have a question: in our recursion function, we are actually passing the same list every time in subsequent recursion call. How does different recursioni call not making chagnes to that list? I've been leetcoding in JS recently and I have to copy the list before I recurse. Looking forward to your answer!
Stuck on this for long. In the tree for target=6, nums={1, 2, 4} the node for target=4, nums={2, 4} i.e. excluding 1, is called twice. Can we not memoize that? I understand the logic of backtracking here, but want to know why nobody tries to improve on this. Is it not possible?
why is "cur" an argument here in the helper function, rather than a globally accessible variable. Doesn't the former method have much worse efficiency?
If you could use any number any number of times, then answer would be infinite with negative numbers. With constraints either like no replacement of element selection or max size of candidates to be selected, we might be able to find answer somehow by modifying the algo.
Can anyone explain why we take a backtracking approach on this problem, and a DP approach to Coin Change 2? It seems the same, given some number of input values that you can use between 0 and infinite times, figure out how you can sum to a target. I know in Coin Change 2 we are just returning the number of solutions rather than the solutions themselves, but I'm not getting why we use a different approach.
because we simply have to create the lists that sums up to the target, its not like you are counting the number of ways u can write the sum to target, yoi actually have to create the lists that why u use backtracking / recursion / bruteforce.
I have the same question. Maybe it is because the possible inputs are way more limited here, so the benefit of saving intermediate results is simply not worth the overhead? In coin change 2 1
in combination sum 2 problem you says the time complexity is n * 2^n since it involves copying the current result array to the final result array. Why is it not n * 2^t here as well?
I am struggling to figure out how to identify if a problem is a backtracking problem, and needs this decision tree treatment. Any help is appreciated!!
My question is when the dfs function return None (if statements happened), code go to dfs(0, [ ], 0) right? So, first time we append value to current and we collected those values, but when the function gives a return, our i, cur, and total should be 0, [ ] and 0. Why code don't see that way and takes cur as [2, 2 ,2 ,2] and total as 8 and pop it, then pass the other function?
the leetcode solution has the time complexity as O(N^(T/m)) where N is the number of candidates, T is the target value, and M is the minimal value among the candidates. It seems like the correct time complexity int the worst case is O(N^T) instead of O(2^T)?
yeah i think you're right. Because the decision tree is an N-ary tree, which means that each node can have up to N nodes (ie. in the example, N = 4 because length of candidates is 4). And yes, because T/m determines max depth of tree, where m is min val of candidates, worst case would be if m = 1, then T/m = T. So O(N^T) worst case makes sense to me.
I am sorry but Time complexity looks wrong because you have n selection in each step because you do not increment index. In subset problem we have 2^n because we increment index even if we dont choose current element
🚀 neetcode.io/ - A better way to prepare for Coding Interviews
Most backtracking problems on leetcode follow this dfs pattern. A lot of them also have this loop inside structure as well. It's pretty easy once you get the gist of it.
This is a genius solution! Once we exhaust a specific number in the candidates (either by going over or hitting the target), we pop back up to the previous call using a new number (in this case it'd be a higher number since the list is sorted and distinct). So we're basically avoiding any previous combinations and building a tree from bottom up, from left to right. Amazing diagram, you're the best NeetCode.
The tree drawing is so good and complete.
Thank you, backtracking is really confusing for me but this visualization is amazing!! Now I use this for all backtracking problems :D
i think the most challenging part of this problem was in knowing how to "traverse" the elements. The base cases are pretty simple (tbh, most recursive graph/tree problems are, but here it's even more straightforward), but it wasn't apparent to me how you'd keep track of repeated elements. In hindsight, this is done by calling dfs at the same index (but making sure to add/remove the element accordingly) and is pretty obvious once you know it.
You are the only decent algo channel on UA-cam. The rest are unintelligible at best. Thanks man.
Bro , you should check out striver, he's great at explaining questions and is one of the best with dsa knowledge and competitive programming.
Channel - TUF
Great explanation. Much better than AlgoMonster. I didn't understand why we could exclude candidates until you explained how each node splits into including or excluding a candidate.
This is very similar to a problem that I’m still looking for a dynamic programming solution for… I was never able to figure it out. Neetcode, you’re my only hope!
This problem should be marked as Hard on leetcode, it's very complex
if you read the solution in leetcode, it is just a dfs tree, except it sorts the candidates, then in the loop, to avoid duplication, you just need to check if the next element is less or larger then the last element in the current combination.
@@liliwen8831 i think the trick for all these kinds of problems is that it is almost always dfs on tree. the number of branches correspond to the number of times you need to recurse. the reason for branching is represented in the call. any time you need to make a decision in a recursion problem, that is a branch on your tree, and you need to exhaust it with dfs.
It would be harder if the nums included options less than 0.
this problem is extremely simple. You just need to know how to solve backtracking problems and specifically how to generate combinations (which is eliminate duplicate combinations)
@@De1n1ol Saying its extremely easy is a huge stretch, I'm willing to bet you had to look up the solution. In that case, it wasn't "extremely easy"
If the cur.append and cur.pop is confusing, you could just add to cur within the recursive call instead:
def dfs(i, curList, total):
if total == target:
res.append(curList)
return
if total > target or i >= len(candidates):
return
dfs(i, curList + [candidates[i]], total + candidates[i])
dfs(i + 1, curList, total)
2 fewer lines of code and you don't have to pop from cur after the first recursive call.
damn what a great catch, that makes the code a lot easier to understand
how is this different from cur.append and curr.pop one neetcode's soln?
the issue with this is you are generating a new list every time you call the function and they need to be cleaned up by the GC. Using the same list with the pop function is memory efficient.
@@meghanasarikonda3104 it's just easier to understand
If you sort inputs. Problem becomes easy.
First populate stack:
For every item at index i > list[-1] not in list. Pop n and put it in a list if sum list < target, then add list to stack.
Then pop a list from the stack and repeat the above continuously for every item in the stack. If the sum of the list == target, add to result. If > target, remove from stack. If < target, add list + [i] to stack.
If you want to save more space you dont need a memo if you take a list of indexes, they will be the same as the memo.
This is iterative and should get every possibility without duplication.
NeetCode you're the best dude keep up the awesome work.
space complexity is O(target val / smallest val in candidates) b/c max depth of the tree is when it keeps adding the smallest element to the combination until it hits or exceeds target.
time: O(number of candidates^max depth)
came up with similar solution, with only 2 parameters for the inner function:
res = []
def backtrack(i, total):
if i == len(candidates) or sum(total) > target:
return
if sum(total) == target:
res.append(total.copy())
return
backtrack(i, total + [candidates[i]])
backtrack(i + 1, total)
backtrack(0, [])
return res
Man, this took me forever to wrap my head around. Either I am too stupid for my desired career path as a non-CS major or this is too difficult for a medium problem.
bro its difficult don't think like that
I found it very interesting to implement this problem with iterative solutions. It translates quite straightforwardly (though it is finicky) to storing the working information on a stack, and then iterating through and processing each node on the stack instead. It taught me a lot about how functional recursion can relate to iterative recursion.
The key is to store all the relevant information on a stack, basically copying how it would be implemented with a function call (ie. function call needs index argument, sum of elements, set of elements), then popping that information off the stack while you process it.
I had a working vector of vectors - each vector within it contained the working set up to that point, then two more variables right at the end containing the current index, and the sum up to that point. Each loop, pop a vector from the stack, process it, and add its children to the stack if its valid (or add the results if they match the requirements). Eventually the stack is empty and you return the results.
The other fun part is it becomes extremely straightforward to convert the iterative implementation to a BFS search instead (checking solutions at the top of the tree instead), by simply converting the stack (I implemented it with std::vector) to a queue (eg. std::deque), and pop the working information from the front instead of the back.
class Solution:
def combinationSum(self, candidates: List[int], target: int) -> List[List[int]]:
res=[]
n=len(candidates)
def comb(arr,ind):
if target < sum(arr):
return
if target==sum(arr):
res.append(arr.copy())
return
for i in range(ind,n):
arr.append(candidates[i])
comb(arr,i)
arr.pop()
return
comb([],0)
return res
Finally, I got an idea of how to do backtracking after some 20 backtracking problems from your channel. I just want to share the code I wrote 😇
Here's my implementation:
class Solution(object):
def combinationSum(self, candidates, target):
"""
:type candidates: List[int]
:type target: int
:rtype: List[List[int]]
"""
ans = []
def dfs(i, curr_sum, curr_lst):
if curr_sum == target:
ans.append(curr_lst[:])
if curr_sum >= target or i >= len(candidates):
return
for j in range(i, len(candidates)):
curr_lst.append(candidates[j])
dfs(j, curr_sum + candidates[j], curr_lst)
curr_lst.pop()
dfs(0,0,[])
return ans
Hey Edward Thanks for the solution .
can you explain me what is the reason behind adding [:] in "ans.append[:]" , i try executing the code without "[:]" and its return the empty list.
And its working with [:] . From my knowledge they are basically doing the same thing i guess
@@ritikdwivedi5983 The [:] is another shortcut to create a copy of the curr_lst and append the curr_lst inside the ans(answer) array.
The reason you want to create the copy and insert into the array is because the curr_lst is constantly changing with values being added and removed as you go through the recursion. I highly recommend debugging and you'll see what I and Neetode meant and why it's vital to include the [:]
The empty list is possibly from the curr_lst.pop(), but that's just a guess lol
The question was literally asked to me in Amazon interview
did u make it to amazon if not where are you working currently.
@@rohitkumaram No I am not working at amazon
Very good approach that outlines a classic use of DFS and backtracking. I solved the problem differently, using a recursive approach, but the issue was the time performance of my algorithm which ended up suffering (bottom 5th percentile!). Thanks for your solution.
Here is the Java code for reference:-
public List combinationSum(int[] candidates, int target) {
Listl=new ArrayList();
backtrack(l,candidates,target,0,new ArrayList(),0);
return l;
}
public void backtrack( Listl, int[] arr, int target, int sum, Listrow, int i)
{
if(sum==target){
l.add(new ArrayList(row));
return;
}
if(i>=arr.length || sum>target){
return;
}
row.add(arr[i]);
backtrack(l,arr,target,sum+arr[i],row,i);
row.remove(row.size()-1);
backtrack(l,arr,target,sum,row,i+1);
}
This is the clearest solution and explanation I have found for backtracking. Thanks for this.
You can also use a for loop, rather than calling out both conditions explicitly.
def combinationSum(self, candidates: List[int], target: int) -> List[List[int]]:
res = []
def backtrack(i, cur):
cursum = sum(cur)
if cursum == target:
res.append(cur.copy())
return
if i >= len(candidates) or cursum > target:
return False
for j in range(i, len(candidates)):
backtrack(j, cur + [candidates[j]])
backtrack(0, [])
return res
After watching previous video, I successfully solved this on my own. Upon reviewing your explanation, I realized that we arrived at the same solution.
So happy that i improved, ty
For the time complexity, since we have to create a copy of cur, which has complexity of O(n), should the time complexity be O(n * 2^ target)?
Yes it should be n*2^n
@@jyotindersingh3458 This is my general understanding of the time complexity (based on Leetcode solution of O(N^T/m)). The decision tree is an N-ary tree, which means that each node can have up to N nodes (ie. in the example, N = 4 because length of candidates is 4). T/m determines max depth of tree, where m is min val of candidates, and T is target. Worst case would be if m = 1, then T/m = T, so a depth of 7. To simplify, O(N^T) worst case makes sense to me.
I use recursion like everyone else. But for this one I wanted to use nested loops! Loop inside loop inside loop and so on :D
我愿称之为算法题最强解析
Great explanation. I think the time complexity is 2 ^ (t/2) because the smallest number is actually 2 so the length of the smallest combination will be t/2 for example if t is 8 the smallest combo is 2,2,2,2 which is 8/2.
Actually the tree suggested, is a very nice solution if you sort the array first.
Then the most left value can only use values from it's right (including itself)
While the farther right you are in the tree / sorted array, you cannot use those values.
Thus you won't create duplicates. And you'll make less calculations then a full on backtrack.
So you can also take unique values only from candidates, and sort them out.
the array can be sorted to avoid extra calls on the exclude side.
4:40 was Gold. Thank you.
'''
how many ways can I sum up to target given a sequence of candidates
'''
answer = []
path = []
def dfs(target, nums):
if target < 0:
return
if target == 0:
answer.append(path.copy())
return
for idx, num in enumerate(nums):
path.append(num)
dfs(target - num, nums[idx:]) #4:40 we dont recurse on the 2. ;)
path.pop()
dfs(target, candidates)
return answer
Some people are really great at teaching. You are one of them ,I have been pulling my hair since last night. I was facing the issue where the solutions were repeating and wasn't sure how to handle it . Thanks a lot ❤
this problem is like Coin Change 2 while the exact combinations need to be reserved, so a dp[target+1] list of lists instead of integers could be used to implement that track. The combinations of all 0~target have to be saved, but it won't need the recursion stack.
Yes I used this approach and it got accepted
We could optimize this solution by sorting nums and stopping recursion if prev element in sorted array itself didn't add up to result
For this example
candidates = [2,3,6,7], target = 7
The usual dfs solution will trace in the below way
2 - 2 - 2 - 2(8 > target) so return
2 - 2 - 2 - 3
2 - 2 - 2 - 6
2 - 2 - 2 - 7
After completing the above pattern only it will move one level up
2 - 2 - 3(7 == target)
if you notice in the first pattern,
already adding up index - 0 which is 2 makes the target bigger
Why do we need to go down on the sorted array by trying the next larger nos?
Thus breaking that level will save considerable time
Complete Code:
def combinationSum(self, nums: List[int], target: int) -> List[List[int]]:
n = len(nums)
nums.sort()
results = []
subset = []
def dfs(target, index):
if target == 0:
results.append(subset.copy())
return
for i in range(index, n):
new_target = target - nums[i]
if new_target >= 0:
subset.append(nums[i])
dfs(new_target, i)
subset.pop()
else:
return
dfs(target, 0)
return results
Leetcode post link: leetcode.com/problems/combination-sum/discuss/2606968/Python-Beats-99.5-one-Tweak-from-usual-dfs-solution
i am absolutely blown away with this backtracking solution( i just started backtracking)
Beautiful explanation/code. It's an eye-opening experience.
I felt like I'm listening to a story :) awesome explanation :)
for append(cur.copy()), the copy() function is actually not supported anymore. Another way to do this is append(cur[:])
curr[:] or curr + []
thx dear But I have two questions
first: what if we start with 0 I think the recursion will not get out of this condition total will not = the target ,i < length of candidates and total < target what is the explanation here
the second what if we found a list that match the target and after that we reach a zero it should make also a list but the code will pop the last element and move to the next index
for example 2 +2 =4 and 2+2+0=4
but the code
cur.pop()
dfs(i +1 ,cur ,total)
solution with sorting
class Solution:
def combinationSum(self, candidates: List[int], target: int) -> List[List[int]]:
dp = {i : [] for i in range(target + 1)}
for candidate in candidates:
dp[candidate] = [[candidate]]
for total in range(1,target + 1):
for candidate in candidates:
for a in dp.get(total - candidate,[]):
new = [candidate] + a
new.sort()
if new not in dp[total]:
dp[total].append(new)
return dp[target]
amazing explanation, the easiest and clearest way i've seen so far thank you so much!
Shouldn't the time compelxity be O(t*2^(nt))? Yes depth is "t", but we start tree from each elements in candidates. Even in the tree you drew, if you don' take a number, you actually start a new tree with that number.
So, for elements [1, 2, 3] and target 4, shouldn't the actual time complexity be:
Starting with 1: 2^4
Starting with 2: 2^4
Starting with 3: 2^4
So, 2^4*2^4*2^4 = 2^(3*4)
Fianlly, in each call we are adding cur array to res. Which has worst case complexity of "t". So, is the final complexity:
O(t*2^(n*t))?
The drawing explanation is top notch, thanks a lot!!
How does the tree diagram represent the code…
You can ask the video a question, but do not expect an answer from it.
great job, there is an error in line 9 it should be "i > len(candidates)"
if you sorted the array in descending order you will get even better solution as you element bigger first reducing the time
we can use memoization to avoid duplicates in the initial tree you drew. so if the set that sum up to target is already present, we do not add it.
after [2,2,3] if you encounter [3,4] its sum is already present but you should still add it
All your videos are so helpful but they would be more helpful if you also went into details about the time and space complexities of your solutions.
can we just rearrange the last 4 lines to avoid pop altogether. Basically mirror the decision tree
class Solution:
def combinationSum(self, candidates: List[int], target: int) -> List[List[int]]:
res = []
def dfs(i, cur, total):
if total == target:
res.append(cur.copy())
return
if i >= len(candidates) or total > target:
return
dfs(i + 1, cur, total)
cur.append(candidates[i])
dfs(i, cur, total + candidates[i])
dfs(0, [], 0)
return res
5:02, that was the piece that I couldn't figure out. Just not including the value when creating the combinations
Thank you so much again, love every single video!
Slight modification where we don't have to add/pop from the list manually. Also, where we use python sugar to copy the list:
class Solution:
def combinationSum(self, candidates: List[int], target: int) -> List[List[int]]:
res = []
def dfs(i, cur, total):
# base case 1), we hit a valid target
if total == target:
res.append(cur[:]) # make sure to pass a copy
return
# base case 2), we are out of bounds or exceeded the target
if i >= len(candidates) or total > target:
return
# need to check both branches: repeating the current candidate, and excluding it
dfs(i, cur + [candidates[i]], total + candidates[i])
dfs(i + 1, cur, total)
# call it with an empty total and empty initial list
dfs(0, [], 0)
return res
I like copying the list here better but this is probably the only time where I would actually rather pop the candidate manually, so that why I can remember what's actually going on in the code.
damn dude! the way you explain everything makes me understand the solution easily,
thanks for the quality content.
a cleaner solution is
class Solution:
def combinationSum(self, candidates: List[int], target: int) -> List[List[int]]:
output = []
def find(options: list[int], total: int, start: int):
# base case
if start == len(candidates) or total > target:
return
for i in range(start, len(candidates)):
item = candidates[i]
if total + item == target:
output.append(options + [item])
elif total + item < target:
find(options + [item], total + item, i)
find([], 0, 0)
return output
thanks for your work
This looks cleaner!
You don't actually need to pass cur into the dfs function (I've learned it from you lol). You could just keep it out and change it dynamically
I think he had to because, dfs is called 2 times recursively , once with i val and other without i val, and without passing , how cur can have 2 values at the same time.
correct me if I am wrong
The returned value is an array of array. You need to push the possible permutation into the answer before clearing it.
Hi, just add how index on input array changes for each branch and solution will become much more easier to comprehend
Absolutly insane to figure this out in 25 minutes alloted.
What doesn't make sense to me in this explanation is why go over the cases where you wouldn't add anything to the array, I think spliting each time between adding and not adding an element is faster and maybe a bit easier to understand for some. I'll leave my solution here if it helps anyone.
class Solution {
public:
vector combinationSum(vector& candidates, int target) {
vector result;
vector subset;
DFS(result, subset, candidates, target, 0, 0);
return result;
}
private:
void DFS(vector& result, vector& subset, const vector& candidates, int target, int sum, int index) {
if (sum >= target) {
if(sum == target) {
result.push_back(subset);
}
return;
}
for(int i = index; i < candidates.size(); i++) {
subset.push_back(candidates[i]);
DFS(result, subset, candidates, target, sum + candidates[i], i);
subset.pop_back();
}
}
};
backtracking has always been my curse :(
I really like all your explanations ,although I code cpp, your explanations with drawings does make a beneficial help.(even for an Asian from tw who speak poor English
Nothing makes me feel more stupid than generating combinations using backtracking. I can do backtracking on matrix without a problem, but as soon as you have combinations or permutations I just get lost even drawing the tree. Like, when we got to [2, 2, 2], I get that adding another two going down the left subtree [2, 2, 2, 2] you get an 8 which is over the target and that's why that branch should stop, but then why didn't we keep going down the right subtree infinitely?
My understanding is that since we keep incrementing i, the pointer for our candidates list, the pointer goes out of bounds, so the the dfs function returns (that was one of our base cases)
What are some simpler backtracking problems I can try to understand the basic concept?
Found this much more approachable once I did a bunch of dynamic programming problems
勉強になりました、とってもありがとうございます
you are so good at this when will I be this good. until then keep on leet coding....
I was able to make it work with the first tree, but the time complexity is bad.
class Solution:
def combinationSum(self, candidates: List[int], target: int) -> List[List[int]]:
res = set()
temp = []
def dfs(total):
if total==target:
res.add(tuple(sorted(temp[:])))
return
if total>target: return
for c in candidates:
temp.append(c)
dfs(total+c)
temp.pop()
dfs(0)
return [list(t) for t in res]
I wrote algorthm quickly but I always struggle to convert them into code. Any suggestion is welcomed.
Thank You So Much NeetCode brother........🙏🏻🙏🏻🙏🏻🙏🏻🙏🏻🙏🏻
Fantastic explanation.
thank you! this vid helped me understand backtracking
why won't it work when I call dfs in the opposite order:
dfs(i + 1, cur, total)
cur.append(candidates[i])
dfs(i, cur, total + candidates[i])
I thought this was cleaner but it gives wrong answer, why is that?
Yeah, me too. I could not figure it out. Let me know if you find it.
You need to pop from curr
if you sort the candidates in descending order it's simpler
sols = []
candidates.sort(reverse=True)
dfs(candidates, target, ())
return sols
def dfs(candidates, target, prefix):
if candidates:
for i, c in enumerate(candidates):
if c > target: # no way to reach the target if all candidates positive
continue
elif c == target: # found a solution, no more possible if all candidates positive
sols.append(prefix + (c,))
else:
dfs(candidates[i:], target-c, prefix + (c,)) # find all solutions starting with c
Why can't we use dfs for not including the element first, then appending it and then dfs for using it? Doing so gives me very strange and wrong outputs.
Eg-
dfs(ctr + 1, nums, curr, total, target)
curr.append(nums[ctr])
dfs(ctr, nums, curr, total + nums[ctr], target)
gives [[7],[7,6,7,6,3,7,6,3,7,6,3,2,7,6,3,7,6,3,2,7,6,3]] for target == 6 and candidates == [2,3,6,7]
whereas using
curr.append(nums[ctr])
dfs(ctr, nums, curr, total + nums[ctr], target)
curr.pop()
dfs(ctr + 1, nums, curr, total, target)
gives [[2,2,3],[7]] as expected?
Hey! Were you able to figure this out?
Any luck finding this out?
I can solve this problem by basing on the solution of subsets that you taught me
This "append" and then "pop" is a little bit confusing.
For me is more intuitive - 1st launch recursive, then append, then launch recursive again. No pops.
Don't forget to copy cur on every recursion call.
Very very well explained Sir. Thank You!!!
I have a question: in our recursion function, we are actually passing the same list every time in subsequent recursion call. How does different recursioni call not making chagnes to that list? I've been leetcoding in JS recently and I have to copy the list before I recurse. Looking forward to your answer!
Nitpick, but root of tree should be shown as `[]`
Stuck on this for long. In the tree for target=6, nums={1, 2, 4} the node for target=4, nums={2, 4} i.e. excluding 1, is called twice. Can we not memoize that?
I understand the logic of backtracking here, but want to know why nobody tries to improve on this. Is it not possible?
it's not easy. Thanks for the explanation.
why is "cur" an argument here in the helper function, rather than a globally accessible variable. Doesn't the former method have much worse efficiency?
I'm so confused by the fact that we are using a single list. I get the idea but so hard to visualize.
took a while to understand but now it makes sense :)
I don't understand why it goes through after the recursive DFS call, cur.pop() should never be reached?
Why copy() is needed? I thought appending cur doesn’t mean that when cur will change it will change whatever already appended.
What if the candidates array can contain negative numbers? How would you modify your current solution?
If you could use any number any number of times, then answer would be infinite with negative numbers.
With constraints either like no replacement of element selection or max size of candidates to be selected, we might be able to find answer somehow by modifying the algo.
Can anyone explain why we take a backtracking approach on this problem, and a DP approach to Coin Change 2? It seems the same, given some number of input values that you can use between 0 and infinite times, figure out how you can sum to a target. I know in Coin Change 2 we are just returning the number of solutions rather than the solutions themselves, but I'm not getting why we use a different approach.
because we simply have to create the lists that sums up to the target, its not like you are counting the number of ways u can write the sum to target, yoi actually have to create the lists that why u use backtracking / recursion / bruteforce.
@@testvb6417 I think the problem changed. The current question requires us to return both (2,2,3) and (2,3,2)
I have the same question. Maybe it is because the possible inputs are way more limited here, so the benefit of saving intermediate results is simply not worth the overhead?
In coin change 2
1
in combination sum 2 problem you says the time complexity is n * 2^n since it involves copying the current result array to the final result array. Why is it not n * 2^t here as well?
I am struggling to figure out how to identify if a problem is a backtracking problem, and needs this decision tree treatment. Any help is appreciated!!
Finally i can understand this,thank you:')
My question is when the dfs function return None (if statements happened), code go to dfs(0, [ ], 0) right? So, first time we append value to current and we collected those values, but when the function gives a return, our i, cur, and total should be 0, [ ] and 0. Why code don't see that way and takes cur as [2, 2 ,2 ,2] and total as 8 and pop it, then pass the other function?
the leetcode solution has the time complexity as O(N^(T/m)) where N is the number of candidates, T is the target value, and M is the minimal value among the candidates. It seems like the correct time complexity int the worst case is O(N^T) instead of O(2^T)?
yeah i think you're right. Because the decision tree is an N-ary tree, which means that each node can have up to N nodes (ie. in the example, N = 4 because length of candidates is 4). And yes, because T/m determines max depth of tree, where m is min val of candidates, worst case would be if m = 1, then T/m = T. So O(N^T) worst case makes sense to me.
Could please also talk about the time and space complexity?
All this experience with developing full stack projects (cloud--based even). But, when it comes to DSA, I lose myself. Sigh!
I am sorry but Time complexity looks wrong because you have n selection in each step because you do not increment index. In subset problem we have 2^n because we increment index even if we dont choose current element
Thanks for the explanation. What is the complexity of your algorithm?
2 pow n
I couldn't understand why we are appending cur.copy() rather than just cur
how does that make a difference?
There is the Depth first search function? You used it before writing it, how to understand the solution after that
Would sorting the candidates list and throwing out larger values if curSum > target improve time complexity?
please upload an solution for traveling salesman and a star algorithms