Combination Sum - Backtracking - Leetcode 39 - Python

🚀 neetcode.io/ - A better way to prepare for Coding Interviews
🐦 Twitter: / neetcode1
🥷 Discord: / discord
🐮 Support the channel: / neetcode
Twitter: / neetcode1
Discord: / discord
⭐ BLIND-75 SPREADSHEET: docs.google.com/spreadsheets/...
💡 CODING SOLUTIONS: • Coding Interview Solut...
💡 DYNAMIC PROGRAMMING PLAYLIST: • House Robber - Leetco...
🌲 TREE PLAYLIST: • Invert Binary Tree - D...
💡 GRAPH PLAYLIST: • Course Schedule - Grap...
💡 BACKTRACKING PLAYLIST: • Word Search - Backtrac...
💡 LINKED LIST PLAYLIST: • Reverse Linked List - ...
Problem Link: neetcode.io/problems/combinat...
0:00 - Read the problem
1:36 - Drawing Explanation
10:19 - Coding Explanation
leetcode 39
This question was identified as an amazon interview question from here: github.com/xizhengszhang/Leet...
#backtracking #combination #python
Disclosure: Some of the links above may be affiliate links, from which I may earn a small commission.

[@NeetCode]

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

[@jonaskhanwald566]

The tree drawing is so good and complete.

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

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

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

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

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

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

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

[@dansheldon6955]

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

[@olanrewajubakare3790]

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

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

[@julesrules1]

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

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

[@yinglll7411]

Thank you so much again, love every single video!

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

[@changlingao4609]

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

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

[@chetansahu1505]

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

[@tehepicduck101]

thank you! this vid helped me understand backtracking

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

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

[@diptilulla2895]

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

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

[@qianchengxx99]

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?

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

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

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

[@satyadharkumarchintagunta3793]

Very very well explained Sir. Thank You!!!

[@weiyaoli6977]

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

[@Kyabaathai353]

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

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

[@masato0908]

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

[@stith_pragya]

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

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

[@sanskaripatrick7191]

Fantastic explanation.

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

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

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

[@yeswanthh5068]

Finally i can understand this,thank you:')

[@eyad880]

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

[@sindhujaraghupatruni7903]

This looks cleaner!

[@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 + []

[@garywasherefirst]

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

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

[@anmolkarki5248]

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

[@AEHCODEMAROC]

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

[@paccini1]

Awesome explanation

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

[@Afr0Afr0]

Absolutly insane to figure this out in 25 minutes alloted.

[@mohammedabulsoud1819]

it's not easy. Thanks for the explanation.

[@RandomShowerThoughts]

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

[@PIRAISUDANB]

Thank u so much for this video

[@dzhangirbayandarov6014]

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

[@vlnd0]

Mate, u r awesome!

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

[@symbol767]

Thank you man

[@wendyyang1885]

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

[@andreybraslavskiy522]

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

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

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

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

[@anthienvo]

Beautiful

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

[@andreytamelo1183]

Thanks!

[@NeetCode]

tysm!!

[@user-oq6ee9lb1n]

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

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

[@chengjinfei8139]

Amazing. So clear, hope added java version as well. And what if Target is a big number like 99?. TC is too big then ? any improvements?

[@mastermax7777]

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

[@sansla710]

@NeetCode You are awesome ....

[@edwardteach2]

U a combination God

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

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

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

[@KartikeyTT]

ty bro

[@kyzmitch2]

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

[@laiwei5931]

backtracking has always been my curse :(

[@yuemingpang3161]

on line 20, why you pass in [ ] instead of res?

[@kirillzlobin7135]

You are amazing

[@Grawlix99]

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

[@user-vu8jp3si2r]

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

[@brookesmyth7094]

Hello, I am new to the concept of recursion, and was wondering the exact logical order of when the two different recursive calls are called and what triggers one to be called but not the other? Does the first dfs call keep on being called until one of the return statements are activated, and then the algorithm executes cur.pop(), and then the second dfs call?

[@reaiswaryaa]

Whatever you mentioned is right, that's how it executes

[@debanjanasarkar6685]

I wrote algorthm quickly but I always struggle to convert them into code. Any suggestion is welcomed.

[@chowdhurylinianazmi5615]

Why copy() is needed? I thought appending cur doesn’t mean that when cur will change it will change whatever already appended.

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

[@Gowtham91mn]

please upload an solution for traveling salesman and a star algorithms

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

[@abhishekpawar8458]

This is like unbounded knapsack

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

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

[@arjunbharadwaj1820]

Hey, why don't you have to cleanup after the second recursive call on line 16?

[@justinUoL]

cur and total stay the same before and after the second call

[@j.y.]

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

[@bharanidharan.m4245]

2 pow n

[@AD-hb6zl]

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

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

[@PippyPappyPatterson]

What's the difference between a subset and a combination?

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

[@aniruddhashahapurkar9244]

Great solution. I am just stumbled upon why we are appending copy instead of just curr itself. Can anyone explain it please?

[@JordanPollard1]

Nitpick, but root of tree should be shown as `[]`

[@zaidachmed868]

cant we just simply use set to avoid the duplicate values? i know i am wrong but why

[@Darkmatterkun]

what is the time complexity for this solution?