Combination Sum - Leetcode 39 - Recursive Backtracking (Python)

[@GregHogg]

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

[@chisomedoka5651]

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

[@anna-plink]

You're not alone!!

[@Johnson_Amah]

You are definitely not alone

[@jithendragunuru]

+1

[@vinaylasetti4665]

Backtracking is a mechanism formed by don't pick a choice and pick a choice approach to arrive at a target solution combination. As per my understanding, we can use backtracking technique whenever we have to deal with combinations. So If you ask why Backtracking? because without backtracking we would endup in duplicate combination of solutions. I hope this gives some light! Thanks

[@ohmyoni]

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

[@GregHogg]

Oh I'm really glad to hear that. Such a tricky topic, I'm glad I did okay 😊

[@saleheen12]

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.

[@jst8922]

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

[@mohammadrafi895]

You wanna teach too?

[@BluAngy]

That is Miro

[@JoeTan-nq4fq]

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]

[@alichopping2703]

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