Combination Sum II - Backtracking - Leetcode 40 - Python

0:00 - Read the problem
2:22 - Drawing Explanation
10:27 - Coding Explanation

leetcode 40

#combination #backtracking #python
Disclosure: Some of the links above may be affiliate links, from which I may earn a small commission.

[saidjahonmamirov]

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

[siqb]

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

[xinniu]

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

[jamesvoynow]

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.

[rahul]

Code that reuses Neetcode's concept from Combination Sum 1. A lot easier to remember the pattern.

class Solution {

List<List<Integer>> result;

public List<List<Integer>> combinationSum2(int[] candidates, int target) {

result = new ArrayList<>();

if (candidates == null || candidates.length == 0)
{
return result;
}

Arrays.sort(candidates);

List<Integer> currSet = new ArrayList<>();

dfs(candidates, 0, currSet, target);

return result;
}

private void dfs(int[] candidates, int index, List<Integer> currSet, int target)
{

// good base case
if (target == 0)
{
List<Integer> 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


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

[abhishekpawar]

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

[vvsish]

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<len(candidates) and
i+=1
dfs(curr, i+1, tot)

dfs([], 0, 0)
return res

[Mohammad-woyi]

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

[DavidDLee]

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.

[adithyanvinod]

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

[naman]

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.

[uniquename]

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

[oxyht]

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

[MethyleneBlue]

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!

[andresivanmonterocassab]

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

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

[CharlesMacKay]

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

[NhanSleeptight]

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

[Mohammad-woyi]

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

[tanishbansal]

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

[minciNashu]

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

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