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
Master Data Structures & Algorithms For FREE at AlgoMap.io!
why is backtracking so hard!!!!!!! I feel dumb, thanks for you explanation. Currently watching for the fifth time
You're not alone!!
You are definitely not alone
+1
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
Seriously this channel is so underrated
I really like these recursive backtracking problems, you explain them well.
Oh I'm really glad to hear that. Such a tricky topic, I'm glad I did okay 😊
This can be easily solved using knapsack approach - dynamic programming.
These videos are great, can you do one for Combination Sum II?
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]
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.
What tool you use for digital whiteboard (3:43) ?
You wanna teach too?
That is Miro