CHEFINSQ : Long challenge video editorial

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.


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 :slight_smile:

That is a good approach too :+1:

1 Like

looks like you are good in dp.

1 Like

Recently started but errichto videos helped me in getting the concepts.

1 Like

can anyone tell me why this code isn’t working?

As with other solutions, it fails on the testcase here.

1 Like

added constraint, but didn’t help… same issue