Combination Sum - Leetcode 39 - Recursive Backtracking (Python)

Please check my playlists for free DSA problem solutions:

My Favorite Courses:

Data Structures & Algorithms:

Python:

Web Dev / Full Stack:

Cloud Development:

Game Development:

SQL & Data Science:

Machine Learning & AI:

[GregHogg]

Master Data Structures & Algorithms For FREE at AlgoMap.io!

[chisomedoka]

why is backtracking so I feel dumb, thanks for you explanation. Currently watching for the fifth time

[ohmyoni]

I really like these recursive backtracking problems, you explain them well.

[shanky]

Seriously this channel is so underrated

[JoeTan-nqfq]

Using a for..loop seems easier

def dfs(index: int, remainder: int, state: list) -> None:
# Base Case

if remainder < 0: return
if remainder == 0: return result.append(state[:])


# Backtrack when the remainder is less than 0
for i in range(index, n):
if (x := remainder - candidates[i]) >= 0:
dfs(i, x, state + [candidates[i]])
else:
return

[2, 3, 5], 8
index = 0 1 2
canddidates[i] = 2, 3, 5 3, 5 5


/ | \
i=0 __[2]__ [3] [5]
/ \ / \
i=0 [2, 2] [2, 3] [3, 3] [3, 5]
/ \ |
i=0 [2, 2, 2] [2, 2, 3] [2, 3, 3]
|
i=0 [2, 2, 2, 2]

[saleheen]

The graph showed in the video hurt my brain but when I saw the code. I realized, it's almost the same code as "Subsets" problem.

[nithinbosej]

On the third level, the right branch of [2], why isn't it already a [2, 3]? Why is it duplicating [2] from its parent to its right branch? X
I mean, why is it drawn like this? @3:45
*[2]*
/ \
[2, 2] *[2]*

Instead of:
[2]
/ \
[2, 2] [2, 3]

[ZKachmer]

What's this decision tree called? Does it have a specific name?

[bigk]

For whatever reason, my output comes out backwards ([[7], [223]]) to the example being shown ([[2, 2, 3], [7]]).

[alichopping]

These videos are great, can you do one for Combination Sum II?

[prakashprabhu]

why are you using curr_sum as argument, why not just do sum(sol) inside the function

[sutendramirajkar]

This can be easily solved using knapsack approach - dynamic programming.

[nekdo_pac]

What tool you use for digital whiteboard (3:43) ?