I rerecorded this solution and made it much better, please watch this instead: kzfaq.info/get/bejne/fLWphdN_urmqlXU.html

I solved it without using a for loop as it made more sense for me. But, this combines all of neetcodes previous solutions on subsets II and combinations: def combinationSum2(self, candidates: List[int], target: int) -> List[List[int]]: def backtrack(i, path, total): if total == target: res.append(path[:]) return if i >= len(candidates) or total > target: return path.append(candidates[i]) backtrack(i+1, path, total + candidates[i]) path.pop() while i+1 < len(candidates) and candidates[i] == candidates[i+1]: i = i + 1 backtrack(i+1, path, total) candidates.sort() res = [] backtrack(0, [], 0) return res

Great explanation. for me it was easier to use logic of previous Neetcode solutions. It is not as fast as yours but easier to understand. Thanks brother for making such content :) class Solution: def combinationSum2(self, candidates, target): res = [] candidates.sort() def dfs(i, cur, total): # Base cases if total == target: res.append(cur.copy()) return if i >= len(candidates) or total > target: return cur.append(candidates[i]) dfs(i + 1, cur, total + candidates[i]) cur.pop() while i + 1 < len(candidates) and candidates[i + 1] == candidates[i]: i += 1 dfs(i + 1, cur, total) dfs(0, [], 0) return res

this is great, but still struggling to understand why this works LOL

Again a brilliant explanation. Two of the optimizations to stop searching if the values or sums get bigger than target were not included in the code so this runs a bit faster: class Solution: def combinationSum2(self, candidates: List[int], target: int) -> List[List[int]]: candidates.sort() res, curr = [], [] def backtrack(curr, pos, remain): if remain == 0: return res.append(curr[:]) prev = -1 for i in range(pos, len(candidates)): if prev == candidates[i]: continue elif remain - candidates[i] < 0: break curr.append(candidates[i]) backtrack(curr, i + 1, remain - candidates[i]) curr.pop() prev = candidates[i] backtrack(curr, 0, target) return res

Neetcode you're the man, and I will always come back to your videos. I hope this doesn't come across rude as I have a ton of respect for you, but I want to say that this coding explanation was not up to your typical high standards. Just wanted to give some hopefully helpful feedback if you were looking to re-do some of these tutorials.

For the people who wants Combination - 1 Style (***Credit - Halal Milksheikh ) Kill it :) class Solution: def combinationSum2(self, candidates: List[int], target: int) -> List[List[int]]: res=[] candidates.sort() def dfs(curr,i,tot): if tot==target: res.append(curr.copy()) return if i>=len(candidates) or tot>target: return curr.append(candidates[i]) dfs(curr,i+1,tot+candidates[i]) curr.pop() while i+1

I think the time complexity should be O(n * 2^n) instead of O(2^n) since we do a copy of the solution array at the end of every path. Actually it’s so weird for me that this problem’s time complexity is said to be O(2^n) while a very similar problem like Subset II is only O(n * 2^n).

Your videos are *usually* very good at explaining the algorithm. This one is not. Looks like you explained one algorithm and coded another. In particular, in the decision tree (7:32) you have one branch which can choose 1s and another that may not include any 1s. There's no place in the code where you never use the same value again, as you backtrack with i + 1 (the next candidate can be the same value as current), which means that there's no such branch as never use 1 again.

Code that reuses Neetcode's concept from Combination Sum 1. A lot easier to remember the pattern. class Solution { List result; public List combinationSum2(int[] candidates, int target) { result = new ArrayList(); if (candidates == null || candidates.length == 0) { return result; } Arrays.sort(candidates); List currSet = new ArrayList(); dfs(candidates, 0, currSet, target); return result; } private void dfs(int[] candidates, int index, List currSet, int target) { // good base case if (target == 0) { List currCopy = new ArrayList(currSet); result.add(currCopy); return; } // bad base cases if (target < 0) { return; } if (index >= candidates.length) { return; } // two decisions: we can add this current number to our result // or we can ignore this number and do a dfs for the next number currSet.add(candidates[index]); // this first branch will have all the subsets which contain this currently added number // we can add this number again so index is not changed dfs(candidates, index + 1, currSet, target - candidates[index]); // backtrack currSet.remove(currSet.size() - 1); // skip duplicates while (index + 1 < candidates.length && candidates[index] == candidates[index + 1]) { index += 1; } // second branch will have all the subsets which dont have this current number dfs(candidates, index + 1, currSet, target); } }

Reverse Sorting will help here : We hit the cases where the target is exceeded first. Thus, prune helps here

class Solution: def combinationSum2(self, candidates: List[int], target: int) -> List[List[int]]: res = [] candidates.sort() def dfs(i,cur): if sum(cur) == target: res.append(cur[::]) return if sum(cur) > target or i >= len(candidates): return for j in range(i,len(candidates)): if j>i and candidates[j] == candidates[j-1]: continue cur.append(candidates[j]) dfs(j+1,cur) cur.pop() dfs(0,[]) return sorted(res) i found this better and more easy to understand

For ones who want similar solution from the first Combination Sum (I used JavaScript in this case): var combinationSum2 = function(candidates, target) { candidates.sort((a, b) => a - b) const res = [] function dfs(pos, cur, total){ if(total === target){ res.push([...cur]) return } if(pos === candidates.length || total > target){ return } cur.push(candidates[pos]) dfs(pos + 1, cur, total + candidates[pos]) while(pos + 1 < candidates.length && candidates[pos] === candidates[pos + 1]){ pos++ } cur.pop() dfs(pos + 1, cur, total) } dfs(0, [], 0) return res };

For those who didn't understand how [1,1,6] is reached, when traversing the first 1, we are backtracking for the next index, there initial 1 will be used. For the second iteration of for loop, we will have only one 1. Reply if it doesn't make sense.

The code for combination 1 and while loop from subsets 2 is muh easier.

based of combination sum 1 and subset 2 : class Solution: def combinationSum2(self, candidates: List[int], target: int) -> List[List[int]]: res = [] candidates.sort() def dfs(i,cur,total): if total == target: res.append(cur.copy()) return if i >= len(candidates) or total > target : return cur.append(candidates[i]) dfs(i+1, cur, total + candidates[i]) cur.pop() while i + 1 < len(candidates) and candidates[i] == candidates[i+1]: i += 1 dfs(i + 1, cur, total) dfs(0,[],0) return res

Why didn’t you solve it like your solution for Subset II?

Remembering previous element and all that, you made this program look different from the combination sum 1 program. The only change that can be done from the combination sum 1 program is the second recurse call can just take index from the next non-duplicate element. just a one liner change from sum-1.

Hey man, just wanted to say you’re doing amazing things on this channel. Btw, do you have longest palindromic subsequence on your to-do list? Thanks!

Combining the solution of combinationSum1 and subsets2: def combinationSum2(self, candidates: List[int], target: int) -> List[List[int]]: # n = len(candidates) , t = target, min_c = min(candidates) # Time O( n ^ (t/min_c + 1) + nlog(n)) = > O( n ^ (t/min_c + 1)) # Space O(t/min_c) ans = [] curr_sum = [] candidates.sort() def backtrack(idx, total): if total == target: ans.append(curr_sum[:]) return if idx >= len(candidates) or total > target: return # left choice curr_sum.append(candidates[idx]) backtrack(idx + 1, total + candidates[idx]) curr_sum.pop() # right choice while idx + 1 < len(candidates) and candidates[idx] == candidates[idx + 1]: idx = idx + 1 backtrack(idx + 1, total) backtrack(0, 0) return ans

The code is diff from what you explained 😣. Explained include or exclude approach but coded iterated version

I think this question is a hard (though it is marked medium) one until one knows the trick. If given in an interview for the first time I'll probably use a set to avoid duplicate combination but that will surely exceed the time limit.

Ok for the people who want a Combination Sum I style of solution for this problem you gotta do 3 things. Sort the candidates, call i+1 on your first dfs and then before your second dfs, advance the pointer past the duplicates like this while (i + 1 < candidates.length && candidates[i] == candidates[i + 1]) { i++ }

your explanation and code are different you explained based on include or not in a level but coded in loop for each level

Good attempt. But, it's unclear how we ended up with [1,1,6] if previous and current elements are the same.

Do you think it's better to try to reuse the code of Combination Sum 1 for this question (just adding a while loop to check for sorted duplicates)?

Optimisation which gives memory usage less than 87% of the submitted sols def get_combination(start,target,temp): prev=-1 for i in range(start,length): if candidates[i]==prev: continue if target-candidates[i]=0: temp.append(candidates[i]) if target-candidates[i]==0: ans.append(temp[:]) temp.pop() return get_combination(i+1,target-candidates[i],temp) temp.pop() else: return prev=candidates[i] ans=[] candidates=sorted(candidates) length=len(candidates) get_combination(0,target,[]) return ans

this one was tricky due to skipping duplicates. I like the usage of the prev variable. this made it very clean and logically solid.

The way I understood the reqt for prev is that practically we are using different counts of the same element and brute forcing and prev==candidates[I] helps to avoid choose a permutation for the elements chosen

Very well worded, thanks. This skip all ones trick is a difference between TLE and accepted.

For those looking for a solution that is still python, but commented with easy to grasp rationale: class Solution: def combinationSum2(self, candidates: List[int], target: int) -> List[List[int]]: candidates.sort() combos = [] combo = [] def backtrack(i=0, localSum=0): # Base cases if localSum == target: combos.append(combo.copy()) return if i == len(candidates) or localSum > target: return # Spawn decision tree for choosing current index. # Reset the decision after (pop) combo.append(candidates[i]) backtrack(i+1, localSum + candidates[i]) combo.pop() # Advance index to the next non-equal digit to avoid duplicates, # then spawn a tree with the null decisiong (same target). while i+1 < len(candidates) and candidates[i+1] == candidates[i]: i = i + 1 backtrack(i+1, localSum) backtrack() return combos

Instead of this, you can just add a while loop to skip over the duplicate elements, like so - (Basically an udpated version of the Combination Sum I code, in C++) class Solution { public: void dfs(int i, vector cur, int total, vector &res, int &target, vector &candidates){ if(total == target){ res.push_back(cur); return; } if(i >= candidates.size() or total > target) return; cur.push_back(candidates[i]); dfs(i + 1, cur, total + candidates[i], res, target, candidates); cur.pop_back(); while(i < candidates.size()-1 and candidates[i] == candidates[i+1]) i++; dfs(i + 1, cur, total, res, target, candidates); } vector combinationSum2(vector& candidates, int target) { vector res; sort(candidates.begin(), candidates.end()); dfs(0, {}, 0, res, target, candidates); return res; } };

If there were two options at every spot, why is there just one backtrack function in the code and not two ? In the final code, it seems like the only backtrack function used will skip over similar values but I do not see the one that should use the same values ?

Python version of modified Combination Sum 1 def combinationSum2(self, candidates: List[int], target: int) -> List[List[int]]: res = [] candidates.sort() def bt(subset, pos, t): # base cases if t == 0: res.append(subset[:]) return if t < 0 or pos >= len(candidates): return # left subset.append(candidates[pos]) bt(subset, pos + 1, t - candidates[pos]) # right, skip completely until distinct candidate subset.pop() while pos + 1 < len(candidates) and candidates[pos] == candidates[pos + 1]: pos += 1 bt(subset, pos + 1, t) bt([], 0, target) return res

you can use most of the same code in 90. Subsets II. the concept of two problems is how to deal with duplicates.

I solved it using the patterns of both Combination Sum and Subsets II class Solution { public void dfs(int i, List combination, List combinations, int[] candidates, int sum, int target) { if (sum == target) { combinations.add(new ArrayList(combination)); return; } if (sum > target || i >= candidates.length) return; combination.add(candidates[i]); dfs(i + 1, combination, combinations, candidates, sum + candidates[i], target); combination.remove(combination.size() - 1); while (i + 1 < candidates.length && candidates[i + 1] == candidates[i]) i++; dfs(i + 1, combination, combinations, candidates, sum, target); } public List combinationSum2(int[] candidates, int target) { List combinations = new ArrayList(); Arrays.sort(candidates); dfs(0, new ArrayList(), combinations, candidates, 0, target); return combinations; } }

I really logically struggle to understand the time complexity of this problem and why its 2N. We can include 10, but if not we could skip it in our FOR LOOP, but if we skip it that doesn't mean we are calling the recursion on nothing. We just go to the next number, 1 in our case, then try that, lets assume 1 also didn't work, then we go to 2, then 7, etc. Super confusing...

can be solved just by adding one condition in combination sum I problem -- def combinationSum2(self, candidates: List[int], target: int) -> List[List[int]]: res = [] candidates.sort() def dfs(i, cur, total): if total == target: res.append(cur.copy()) return if i >= len(candidates) or total > target: return cur.append(candidates[i]) dfs(i+1, cur, total+candidates[i]) cur.pop() #to avoid duplicate while (i+1 < len(candidates) and candidates[i] == candidates[i+1]): i = i+1 dfs(i+1, cur, total) dfs(0, [], 0) return res

Happy Daily

I tried your solution with test case ([10,1,2,7,6,1,5], 8), and the result is missing [1, 1, 6]. Somehow it also skips adding the second number 1 there even thou it's valid

I found out your channel by searching dp problems. Great explanations man! Subscribed instantly

Guys just use the same code as that of subset 2 and just add extra base condtions where you exceed the sum and where you find the sum

man, thank you for the explanation! clean & neet

What was also a bit confusing was that the decision tree that was drawn has 2 branches whereas the code has N branches staring from the root, is that right or am I missing something here? Wouldn't the runtime of this be more like N^N as the branching factor is N and not 2?

How neatly u explain man! Awesome 😎

What will be the time complexity of this approach? I feel it will be 2^N where n is the number of unique elements in the list. What do you think?

I dont get it. We have two ways: use number in combination or skip it. With backtrack(cur, i+1, target - candidates[i]) we use current number in combination. But in which part of code we dont use that number and skip it? Please explain

Thanks neetcode, really like your videos!

So simple.. thank you!

I prefer the 0/1 knapsack DP aproach to this problem, but pretty sure the time complexity is 2^N * T, where T is the target since you have to traverse the dp array for each number. Hope this helps those who aren't great at backtracking, like myself... def combinationSum2(self, candidates, target): candidates.sort() dp = [set() for _ in range(target+1)] dp[0].add(()) for num in candidates: for i in range(target, num-1, -1): for subSet in dp[i-num]: subSet += (num,) dp[i].add(subSet) return dp[-1]

Why can't this be implemented as a binary DFS/backtrack? Each branch would decide whether or not a certain-indexed candidate is included. For reasons I don't understand, I can only get this to work with an n-ary implementation. In other words, why is the binary decison whether we include any 1 instead of any particular instance of 1?

Thanks a lot for the video. I love it. I just got a question: isn't the tree to illustrate your code should be like, first level: [], second-level [1] [1] [2]...[7][10], and then, the children of first left child of second-level be [1][2]...[7][10] ? Note that the for loop starts with all the elements in the range, instead of a take or not take binary tree.

Why isn't the time complexity n*2^n ? You have to make a copy of each combination to add to the return array

I think this problem allows us to have the duplicate numbers if they are on different indices.

thanks for the explanation!

Great solution. I couldn't figure out how to get rid of the duplicates by myself. I tried everything, sets, hashMaps, even using the return of the backtrack function to eliminate the used nums from candidates. Nothing worked =/

Great explanation, thanks!

Wow the only missing thing for me is i > start this was the reason my answer was not getting accepted

Can we not use a hashmap ? Honestly I found the explanation very confusing

Can't we just take set of input list and reuse combination sum I solution?

If you continue to extend the tree you made in your drawing explanation, won't you find duplicates?

Why do you do target - candidates[i] as opposed to storing a total and adding candidates[i] like for combination sum I?

Why is this time we are subtracting value from target, not summing up values to reach target?

im pretty sure the code is different from the decision tree he showed lol. The decision tree he showed is a binary tree but his code isn't.

u can also break since they are sorted on bigger value

Why is the time complexity of this solution not O(n * 2^n) like the Subsets II problem?

Instead of initializing prev to -1, why don't you initialize it to None? Can python compare a None and an int?

when I tried your solution code it didn't work so I replaced 'for i in range(len(candidates))' with 'for j in range(i, len(candidates))' and it did work. Can you guys explain why is that?

class Solution: def combinationSum2(self, candidates: List[int], target: int) -> List[List[int]]: candidates.sort() result = [] curr = [] def backtrack(start, target): #base case 1 if target == 0: result.append(curr.copy()) return #base case 2 if target < 0: return for i in range(start, len(candidates)): #handling duplicate elements if i > start and candidates[i] == candidates[i - 1]: continue curr.append(candidates[i]) backtrack(i + 1, target - candidates[i]) curr.pop() if target

Is there a reason why you deviated from the pattern used in Combination Sum I ???

Why can't we use this one instead at line 14-15? if i + 1 < len(candidates) and candidates[i] == candidates[i+1]: continue As we did in subset problem with duplicates?

Just realized that the technique here is the same as #90

time complexity ?

You should remake this video. It's hard to follow for the first time when it's full of incorrect logic and then only later cleaned up right before ending

the code doesnt match the explanation. In the explanation you were making 2 decisions....but in the code the number of decisions is decided b the loop

How do you print it….

God Im so terrible at this rip

class Solution(): def dfs(self, arr, index, target, isIncluded, path=[]): if target == 0: self.result.append(path) return if index < len(arr) and target < arr[index]: ## this condition speeds up the programme a lot as lot of negative cases are coming return self.dfs(arr, index+1, target, False, path) if index == len(arr): return else: self.dfs(arr, index+1, target, False, path) if index > 0 and arr[index-1] == arr[index] and not isIncluded: return self.dfs(arr, index+1, target-arr[index], True, path+[arr[index]]) def combinationSum2(self, arr, target): self.result = [] self.dfs(sorted(arr), 0, target, False) return self.result

Bounded knapsack

Why are you calling target - candidates[i] at the recursive function? Word of advice, you should run a step by step demonstration of your code and make your explanation without rushing, as it feels you just want to finish up the video as quickly as possible.

5:17

Doesn't the time complexity become O(n!) because we choose n elements in the first choice, n-1 elements for the second layer and so on? Can you clarify this please..

Am I really that dumb?

Dont look at this. There is an easier answer on leetcode

based of combination sum 1 and subset 2 : class Solution: def combinationSum2(self, candidates: List[int], target: int) -> List[List[int]]: res = [] candidates.sort() def dfs(i,cur,total): if total == target: res.append(cur.copy()) return if i >= len(candidates) or total > target : return cur.append(candidates[i]) dfs(i+1, cur, total + candidates[i]) cur.pop() while i + 1 < len(candidates) and candidates[i] == candidates[i+1]: i += 1 dfs(i + 1, cur, total) dfs(0,[],0) return res