combination sum | combination sum leetcode | leetcode 39 | backtracking | Amazon Facebook Adobe

#Backtracking #Combination #Sum #Combination_Sum #Code #Interview #Practice #September #Leetcode #Medium #39 #Algorithm #DataStructure #Java #Preparation #NG #nickode #CookCodeTravel #CCT

[password]

the easiest backtracking approach i have seen til now...awesome!!!

[Fakipo]

Loved it man, I am new to backtracking, and trying to learn it gradually. Thanks for explaining it in such a detailed and coherent manner.

[AmbarDudhane]

very good approach. Wrote on paper and then I understood the algorithm. Simple and effective.

[jaimeeduardo]

I understand but the complexity should be too big because the constraints for n = 30 and for the target is 500 so it in theory can be 30^500, anyways good video

[midhileshmomidi]

In Python

dp = [[] for _ in range(target+1)]

for c in candidates:
for i in range(0, target+1):
if i<c:
continue
if i==c:
dp[i].append([c])

else:
for j in dp[i-c]:
dp[i].append(j + [c])

return dp[target]

[aniinfonet]

can you please explain why we are adding new ArrayList(list) instead of just list.why it is empty when we add just list

[ankurchaudhary]

we can return after adding list into result arraylist.

[NareshGupta]

Try out other Combinations Sum problem 2, 3, 4 etc.

[sripolisettys]

This solution is not avoiding duplicates.

[Bakasta]

but how will we restore the original value of the target which will become negative during backtrcking, please clear it :)

[jxwnwgo]

hi, could you help me understand how the target is getting "re-updated" to the original target once a valid list is found?? I got that we're removing the last element from the list to go back up one level, but how do we ensure the target would be updated?

[sanukumar]

can you please explain ho ur avoiding duplicate

[naveen]

How does it not print the permutations of (2, 2, 3)?

[aditya]

still not clear why we are doing result.add(new ArrayList(list)); instead of result.add((list)); as we have already passed list as an object when calling the backtrack function.

[pleasesirmorevideos]

sir i understood combination sum 1, 3 and 4 but in 2 i dont know how to optimize it by ignoring repetitions

[DMA-I]

I am so confused . Isn't this solution generating duplicates like [2, 2, 3] and [3, 2, 2]?

[harishkandikatla]

What's the time complexity for DP based solution? Is this better than DP?

[pradeepmondal]

Ok ..thank you sir ... But is there any other efficient way of solving this ???

[shubhamladha]

Watch good teacher for better understanding.

[dipakgupta]

Can anyone explain to me the time complexity of this solution?