Combination Sum - Backtracking - Leetcode 39 - Python

[@NeetCode]

🚀 neetcode.io/ - A better way to prepare for Coding Interviews

[@jonaskhanwald566]

The tree drawing is so good and complete.

[@SM-si2ky]

Thank you, backtracking is really confusing for me but this visualization is amazing!! Now I use this for all backtracking problems :D

[@navaneethmkrishnan6374]

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.

[@MandlyL]

You are the only decent algo channel on KZbin. The rest are unintelligible at best. Thanks man.

[@gamerspoint4256]

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

[@Andrew-dd2vf]

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.

[@spacetoast7783]

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.

[@dansheldon6955]

NeetCode you're the best dude keep up the awesome work.

[@dave6012]

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!

[@dorondavid4698]

This problem should be marked as Hard on leetcode, it's very complex

[@liliwen8831]

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.

[@kirbykidsmith]

@@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.

[@josephvictory9536]

It would be harder if the nums included options less than 0.

[@De1n1ol]

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)

[@symbol767]

@@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"

[@jamestruong3320]

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.

[@MichaelShingo]

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.

[@row-v8o]

damn what a great catch, that makes the code a lot easier to understand

[@meghanasarikonda3104]

how is this different from cur.append and curr.pop one neetcode's soln?

[@hakansify]

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.

[@DankMemes-xq2xm]

@@meghanasarikonda3104 it's just easier to understand

[@pcog1216]

The question was literally asked to me in Amazon interview

[@rohitkumaram]

did u make it to amazon if not where are you working currently.

[@pcog1216]

@@rohitkumaram No I am not working at amazon

[@olanrewajubakare3790]

This is the clearest solution and explanation I have found for backtracking. Thanks for this.

[@VladimirTheAesthete]

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.

[@kaushik.aryan04]

bro its difficult don't think like that

[@jordanb722]

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.

[@weiyaoli6977]

我愿称之为算法题最强解析

[@junyuchen6413]

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)?

[@jyotindersingh3458]

Yes it should be n*2^n

[@George-qr3tr]

@@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.

[@andreytamelo1183]

Thanks!

[@NeetCode]

tysm!!

[@Iamine1981]

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.

[@PhanNghia-fk5rv]

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

[@michaelalemu3979]

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

[@julesrules1]

Beautiful explanation/code. It's an eye-opening experience.

[@josephvictory9536]

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.

[@tahaiftekhar6466]

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

[@asishgokarakonda9336]

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 😇

[@chetansahu1505]

I felt like I'm listening to a story :) awesome explanation :)

[@changlingao4609]

amazing explanation, the easiest and clearest way i've seen so far thank you so much!

[@galkk3]

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

[@maks029]

when you're doing sum(total) it's going to do unnecessary re-computation of the sum every level you go to... so it's worse time complexity, especially as the number of nums and target grows.

[@Tygelin86]

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.

[@yitongxie6574]

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.

[@devanshsanghavi]

Yes I used this approach and it got accepted

[@HarshaVardhan-pj5gp]

The drawing explanation is top notch, thanks a lot!!

[@diptilulla2895]

the array can be sorted to avoid extra calls on the exclude side.

[@yinglll7411]

Thank you so much again, love every single video!

[@RandomShowerThoughts]

5:02, that was the piece that I couldn't figure out. Just not including the value when creating the combinations

[@allensun6329]

for append(cur.copy()), the copy() function is actually not supported anymore. Another way to do this is append(cur[:])

[@aryashah6069]

curr[:] or curr + []

[@mohamedyoussef7209]

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)

[@EranM]

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.

[@ZubairKhan-fw9dp]

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)

[@adembaccara4805]

what about using set as result to avoid duplicates and then convert it back into a vector.

[@edwardteach2]

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

[@ritikdwivedi5983]

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

[@edwardteach2]

@@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

[@saurabh2802]

i am absolutely blown away with this backtracking solution( i just started backtracking)

[@ahmedamr1124]

if you sorted the array in descending order you will get even better solution as you element bigger first reducing the time

[@sneakykk]

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 ❤

[@Kyabaathai353]

damn dude! the way you explain everything makes me understand the solution easily, thanks for the quality content.

[@bikaskatwal9540]

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))?

[@AEHCODEMAROC]

great job, there is an error in line 9 it should be "i > len(candidates)"

[@KostasN-p2i]

Thank you very much for the great content! I was wondering about this problem. Is there a dynamic programming solution of complexity len(N)*target? Similar to the target sum problem.

[@tehepicduck101]

thank you! this vid helped me understand backtracking

[@anyalauria1364]

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?

[@gowthamprakaash1409]

Yeah, me too. I could not figure it out. Let me know if you find it.

[@nikhilaradhya4088]

You need to pop from curr

[@stith_pragya]

Thank You So Much NeetCode brother........🙏🏻🙏🏻🙏🏻🙏🏻🙏🏻🙏🏻

[@HadilCharafeddine]

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.

[@sanskaripatrick7191]

Fantastic explanation.

[@papithecollector]

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.

[@play005517]

after [2,2,3] if you encounter [3,4] its sum is already present but you should still add it

[@zhenmingwang9363]

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!

[@andreybraslavskiy522]

Hi, just add how index on input array changes for each branch and solution will become much more easier to comprehend

[@masato0908]

勉強になりました、とってもありがとうございます

[@findingMyself.25yearsago]

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

[@anmolkarki5248]

you are so good at this when will I be this good. until then keep on leet coding....

[@kaylaelortondo4349]

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.

[@testvb6417]

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.

[@AdityaVarmaMudunuri]

@@testvb6417 I think the problem changed. The current question requires us to return both (2,2,3) and (2,3,2)

[@lohojo111]

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

[@yeswanthh5068]

Finally i can understand this,thank you:')

[@garywasherefirst]

took a while to understand but now it makes sense :)

[@agnelwaghela]

Could please also talk about the time and space complexity?

[@aryanmobiny7340]

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

[@rohitkumaram]

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

[@haha-eg8fj]

The returned value is an array of array. You need to push the possible permutation into the answer before clearing it.

[@tuandino6990]

Man this thing is hard af

[@Afr0Afr0]

Absolutly insane to figure this out in 25 minutes alloted.

[@illu1na]

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?

[@PM-dp1ul]

I don't understand why it goes through after the recursive DFS call, cur.pop() should never be reached?

[@BirinderSingh]

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?

[@kartiksoni825]

Hey! Were you able to figure this out?

[@gowthamprakaash1409]

Any luck finding this out?

[@mastermax7777]

10:00 isnt each value in candidates at least 2? not 1? because on leetcode it says.. 2

[@satyadharkumarchintagunta3793]

Very very well explained Sir. Thank You!!!

[@jasonnnbourne]

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?

[@kyzmitch2]

There is the Depth first search function? You used it before writing it, how to understand the solution after that

[@robyc9545]

What if the candidates array can contain negative numbers? How would you modify your current solution?

[@dwaraganathanrengasamy6169]

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.

[@n.h.son1902]

I can solve this problem by basing on the solution of subsets that you taught me

[@rohanb9512]

Isn't O(2 ^ t) too high for the constraints mentioned where 1

[@annieonee]

Could someone help explain in more details why the time complexity is O(target)? Thank you!

[@TheRacingmanic]

Cause you're gonna be going down target(T length) of nodes in the tree and since its always a decision of 2 choices in a binary tree you get 2^T

[@dheepthaaanand1133]

maximum height of the tree would be max possible length of combination. That would be when you have a 1 in your set so max possible length would be target/1 = target

[@taufiqrahman2363]

Any idea what the Space Complexity will be?

[@supremoluminary]

How does the tree diagram represent the code… You can ask the video a question, but do not expect an answer from it.

[@RV-qf1iz]

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); }

[@dzhangirbayandarov6014]

Would sorting the candidates list and throwing out larger values if curSum > target improve time complexity?

[@dreamakash]

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

[@victorcui4014]

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)?

[@George-qr3tr]

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.

[@sonupatel-rc8ms]

why are we not using curr (list []) variable similar as subsets problem instead of passing curr to function call. is this just another way or we are doing this some specific reason

[@manassalunke1755]

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]

[@MaxFung]

Why do we need to run .copy() on the cur variable? I tried using a new variable, valid_cur, which I tried appending, but it broke the algorithm.

[@카이트-c8y]

Is there any solution that using iterative solution instead of recursion with same logic? (Using Stack)

[@AD-hb6zl]

I couldn't understand why we are appending cur.copy() rather than just cur how does that make a difference?

[@陳阿足-c4n]

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

[@huyennguyenkhai7632]

Hi Neetcoder, can someone please explain why we have to create a copy of curr, what would happen if we dont (append as is).

[@vlnd0]

Mate, u r awesome!

[@drstoneftw6084]

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]

[@wendyyang1885]

I do have one question, would writing the function inside another function or outside the function effect its time complexity

[@Fran-kc2gu]

no

[@user-wf3bp5zu3u]

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

[@ayundaywhea2525]

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.

[@adhirajbhattacharya8574]

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?

[@hbhavsi]

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!!

[@PIRAISUDANB]

Thank u so much for this video

[@pixelgabriel6099]

Sorry, I'm confused. How did the res = [] get updated so we can return it? I don't code in Python, so idk how it works.

[@manassalunke1755]

The nested function( here dfs ) has the access to candidates, target and res. We don't need to explicitly pass them as parameters.

[@RushOrbit]

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?

[@johndong4754]

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)

[@henrydi800]

what is "return" mean in here. I do not understand. Can you or someone explain it for me?

[@NeetCode]

Return in this case is just being used to end the function early, it's not really returning a meaningful value.

[@henrydi800]

@@NeetCode thanks. One more question, what is the cur and total from dfs(i+1, cur, total) ? these two values come from first decision dfs(i, cur, total)? I got confused. Can you give me an example?

[@George-qr3tr]

@@henrydi800 'cur' stores currently selected numbers, and 'total' is the current sum of the currently selected numbers. Hope this helps.

[@j.y.]

Thanks for the explanation. What is the complexity of your algorithm?

[@bharanidharan.m4245]

2 pow n