Leetcode - Combination Sum (Python)

[@northridgefield]

1) For non-Python people, "range" is inclusive on start but exclusive on right. It can be misleading as in Kotlin we use 1..target that is inclusive on both ends. 2) Big O: according to chatGPT+ it's hard to be precise about space complexity as it depends on nature of the input, it settled at: O(target × 2^candidates.length). In terms of time complexity: O(n × target × 2^candidates.length). Anyone thinks there's better Big O explanation - leave a comment :) Very cool explanation Tim, thanks.

[@ritteshpv2196]

All your videos are just awesome with best and simple explanation. Also, it would be really great if you could explain explain the Time Complexity and space complexity as well. This is the only extra requirement that every one of your subscriber is wanting from you, please update in description atleast

[@anaken127]

it is match more convinient and faster then the recursion way, thanks!

[@DiaaHaresYusf]

very thanks for this amazing video , I wanted just to mention that candidates does not have to be sorted , logically I tested and i tested by code too. thanks bro

[@darshakmehta]

your videos are always awesome sir. besides, extra clap for whiteboard assisted explanation!! 👏🏻👏🏻👏🏻

[@RajSingh-dl2lk]

great solution, can you explain why is the time complexity is soo less even though there are three loops. Also can we do all the Backtracking problems using DP?

[@KBLive7]

Great vid, clear explanation. Got my sub! Keep them coming!

[@timc3406]

Sure thing! Thank you!

[@wolfwalker_]

that would be great if you could explain on the whiteboard with the example given by leetcode.

[@ArunNalluri]

great way to solve this problem! Thank you! the way you code is a little unconventional but the explanation and approach is excellent!

[@yilmazbingol4838]

smart solution. How did it satisfy the uniqueness?

[@OverLordOfDa3rdWorld]

Dude, you're amazing! Thank you!!!

[@greyreynyn]

Amazing explanation! I am just curious how to decide whether a problem can be solved by DP or not? It seems unintuitive to me to try this approach. Do you have any tips on how to tell when it's worthwhile to try this approach?

[@FlexGC]

If you can break up the problem into smaller subproblems. If the subproblems solved will help you get to the answer more efficently (memoization).

[@greyreynyn]

@@FlexGC That makes sense, I guess logically if 1) you think of calculating the combinations from 0 -> target, and 2) you write the combinations out and notice combinations that sum to larger values are made of parts that sum to smaller values, then the approach should follow. And by figuring out the combinations that sum to smaller values, you can use those later (thats the memo part) I guess it's not immediately obvious to me that the right thing to do is start counting all the different ways to sum to the numbers between 1 and target. Maybe I just need more exposure to these types of problems.

[@Yu-pw2pp]

good videos, very helpful!

[@liwensi1218]

Great video! I am new for python. I am trying to use "blist.append(c)" to replace the "blist+[c]". I got nonetype error. Why?

[@liwensi1218]

Figured it out by myself. the "blist.append(c)" will add c into blist, but the return value will be none. Another thing is append will not create a new list. Here we need copy() the blist first. The below code will be same with dp[i].append(blist + [c]), temp = blist.copy() temp.append(c) dp[i].append(temp)

[@BananaButcher]

@@liwensi1218 great job man. you did well

[@jay-rathod-01]

beautiful

[@jieshi169]

Good job! Thanks for the explanation!

[@timc3406]

You're welcome!

[@xiaoxiaoliu2018]

You are best

[@abhiseka5735]

What is time and space complexity?

[@timc3406]

Honestly not sure... N * N^K maybe?

[@mohammedsafia5434]

@@timc3406 the RunTime is much better than both recursive DFS and Memoized solution. which is 2^n exponential time. Space complexity also almost the same if we take into account the recursion stack storage as well. I think the run time in the worst case for your approach will be N^3. ie. N^2 for moving through 2D DP Table and N for each cell to find all the pair.