Programming Interview : Dynamic Programming :Subset sum problem

Don't forget to Like , Share & Subscribe !!
Check our recent series on:

Connect :

[kuanslove]

This is the best explanation I have ever found by now for this question ! Make me feel that I still have chance to be treated as a normal IQ human but not a stupid pig( I'm not sure if this is the correct way to say that, cos it was said that Piggy has a pretty high IQ )

[YaredFlores]

2019 and this is yet the best explanation I have found for Dynamic programming tabulation strategy. You are brilliant.

[LtKharn]

I think in the final code i and j are the wrong way round, it needs to be <n and j<sum+1, also I think there is a problem in the main logic if you have:
m[i-1][j] || m[i-j][j-a[i]]
when a[i] is bigger than j you'll get an out of bounds error as j-a[i] with be negative.

[RishabSharma]

This is one of the best explanation for subset sum problem.Anyone who wants to understand the concept should must watch this.
Good work folks!
Keep up the good work.

[cybertech]

there is a special case in row 0 m[i-1][j]
will be m[-1][j]
and you should reverse the two loops the first should be i <n and the second should be j<=sum

[ritwiksen]

This is definitely the best explanation that I've found for this question. Nothing fancy, straight to the details.

[danphamtom]

I spent a long time trying to understand this problem and your explanation was the best one I've seen so far!

[trysubbu]

This is the best explanation very short and crisp. There should be some code issue.
initialization of array should be since 0th row is for empty set
boolean [][] m= new boolean [n+1][sum+1];

for (int i=1;i<=a.length;i++) m[0][i]=false; //for the empty set
//Initialize first column
for (int i=0;i<=n;i++) m[i][0]=true;

Then memoization matrix should be formed as given below

for(int i=1;i<=n;i++){
for(int j=1;j<=sum;j++){
m[i][j]= m[i-1][j];
if(m[i][j]==false && j>=a[i-1]){
m[i][j]= m[i-1][j] || m[i-1][j-a[i-1]];
}
}end of jth iterations
}//end ith iterations

[vikasrubi]

Best explanation i got till for this. Everyone was just reading out the algo.. Thanks

[grahamdd]

Well done. You have done a very good job in this presentation. You truly understand the problem and managed to communicate the logic/your understanding to viewers like me. Job very well done! Bravo

[levimckenzie]

The explanation is very clear and concise, good video overall. But there is problem in the code 13:30. You would go out of bounds of the matrix straight away for i=0 and j=0: m[0][0] = m[-1][0] || m[-1][-1]. That being said, the principle is correct, but the code is not finished.

[saketkumarsingh]

It's really crystal clear! Thank you very much ma'am

[polavenki]

Crisp and clear explanation. Worth it.

[rahul-qofi]

Simple transcends genius~Albert Einstein, This is such a simple explanation, thanks

[MrKiran]

isn't it i<n and j<sum+1 in the code given at the end

[androidocean]

Amazing explanation Noopur. One of the best explanation I've ever found till now for this particular question. Keep it up. I came here after reading 12 blogs and Rummaged through youtube and google and many others.

[sanjeeth]

Best explanation for this question.. Others just filling up dp table like donkeys.

[GagandeepSingh-eyri]

You gave a nice intuition of the concept mam.

[prajwaladsul]

Great explanation. Now I have understood the concept of Dynamic Programming. Tysm.

[prakhartech]

Pretty much awesome ! Clear and lucid explanation. Thanks !
Shouldn't be conditional statements for both the for loops, be exchanged ?
i should go from 0 to n and j from 0 to sum and not vice versa?