Difficulty : Easy
suggestions are always welcome for making this channel better.
You guys are requested to support this channel by subscribing.
Thank you.
Happy Coding.
4 Likes
Hey , I solved the question using a different approach. Though it’s inefficient but it works for the given set of constraints and quite straight forward.
1 Like
well it’s so easy problem that almost all solutions seem straight forward.
Yeah I agree with you.
well what was your approach?
I’m not really good at explaining, but I’ll give it a try.
So here’s what I thought :
Say that I’m at i th index, what are the things that I need to know that will help me uniquely identify the state.
Turns out there are three things :
1 -> the current index I’m at
2 -> the current sum that I’ve achieved, and
3 -> the number of elements in the set.
These three things will help me uniquely identify any position/state.
For any index there are two possibilities , either I include that index in the current set or exclude it.
Now the rest part is just backtracking and memoization.
dp[idx][sum][count] = solve(idx-1,sum,count,mins,a) + solve(idx-1,sum+a[idx],count+1,mins,a);
Hope that I was clear enough 
That is a good approach too 
1 Like
looks like you are good in dp.
1 Like
Recently started but errichto videos helped me in getting the concepts.
1 Like