Combination Sum II - Leetcode 40 - Python

0:00 - Read the problem
0:30 - Drawing Explanation
9:08 - Coding Explanation

leetcode 40

#neetcode #leetcode #python

[seanchaney]

My brain is literally expanding right now. I was working on Combination Sum and thought, "Well, if I couldn't reuse candidates, this problem would feel a lot like 3Sum." Then I get to this problem, and boom—lock it in. Sean is popping off.

Pattern recognition is skyrocketing astronomically at 3 AM, while my grades are plummeting because I’m studying this instead. I can’t wait for all this prep to go to waste when I get zero interviews.

[rahulkinger]

Thank you! This is certainly a more intuitive and easy to understand explanation over the previous Combination Sum II video.
I think there is scope for a small optimization, similar to someone already mentioned here; if we are going to be trying an element which when added to total already exceeds target, then we might as well stop recursively calling anymore, simply returning from thereon as no further candidate values will lead to a sum with a cur list to be equal to target, allowing the most recent added element in that list to be popped out faster.


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 total > target or i == len(candidates):
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
if i + 1 < len(candidates) and total + candidates[i + 1] <= target:
dfs(i + 1, cur, total)

dfs(0, [], 0)
return res

[impatientgaming]

another great explanation, thank you so much.

[phoneix]

Dayum. I was so close solving the problem, even sorted the array, somehow I could not wrap my head around the skipping part.

[huilingtang]

I have a question why not do the case 2 which is skip the element first then do the case 1 which includes element? In the way you dont need to pop the element from the cur.

[Kirqos]

I ended up doing this by iterating from i=0 to 2^n-1 and then selecting elements of the array based on the bit pattern of i - this gives all possible combinations, has the same complexity and worked for the challenge inputs.

However, I then realised that this could actually not work correctly for very large arrays due to a) overflow and b) potential unwanted rounding in Math.pow (which is a floating point operation). But I suppose that for that to occur, the arrays would have to be so large that generating all combinations would be way too slow anyway.

[yang]

The solution was simpler than expected

[achadharma]

when order of the if statements (base cases) changes why the code won't work for the input, [2, 5, 2, 1, 2]