DP 14. Subset Sum Equals to Target | Identify DP on Subsequences and Ways to Solve them

a

In this video, we solve the problem subsets sum equal to K. This problem is the first problem on DP on Subsequences Pattern. Please watch this video to have a clear concept of take/notTake concept.

[takeUforward]

I need your support, and you can do that by giving me a like, and commenting "understood" if I was able to explain you.

Note: Please add a check for arr[0] <= target in tabulation code’s base condition.

[ankitadas]

Understood! you ended the video by submitting space optimization code at Morning 02:53 How much energy you have 😱😱😱😱. Hats off to your dedication.

[tanmay]

Had to watch the video multiple times in order to fully understand this concept. In all seriousness, there are so many key points to be kept in mind when learning this concept.

[ParodyCSEDept]

Tbh in most of the previous 13 problems, I was intuitively able to guess the DP recurrence relation (without thinking about recursion and all). However for this question, intuition didn't kick in. Then, I remembered your words that if I can write a recursive solution for the problem then after following your steps, I will be able to reach the DP solution. So I did follow all the steps and yeah I really was able to reach the most optimal solution for this on my own. Hats off to you Striver!
Understood!

[nityanandbhaskar]

Just a edge case correction. dp[0][arr[0]] could give out of bound exception if arr[0] > target. So use a check for that.

[dsp-iocj]

dp[0][arr[0]]=1; in this what if arr[0] is greater than target, coz given constraints are arr[i]<1e9 and k<1e3

[swapan]

Nicely explained! Had to do dry run multiple times for full understanding.
It seems very tough to directly write tabulation/space optimization method, but easy when starting from recursion and following the order.

[MohammadKhan-ldxt]

Before starting this dp series, I was really confused as to which playlist I should follow as there were many good playlist, but after listening to first 2 lectures, I knew that this is the best dp playlist I could ever find and this includes the paid courses too. I have paid courses but I prefer this.
I am addicted to this playlist. Seriously!!! Hats of to you bhaiyya🔥Keep striving and good luck. Hope to see you on the right path..

[lambar]

Your energy and passion for breaking it down is commendable… thanks

[chetanthakral]

I think he is missing a if case, if arr[0] >=k, then we would be getting a sigsegv runtime error.
To remove that we can replace dp[0][arr[0]] = true; by
if(arr[0] <= k) dp[0][arr[0]] = true;

[mr.jacker]

was Asked in Google last year in Interview

[kevinthant]

So far to me, you are the best explainer of algorithm questions on the whole Internet. Thank you so much for your amazing work on these explanation videos. 🙏🙌

[SriAdiNarayanaReddySabbella]

Understood! Tabulation is tricky in this one a little bit. But, your explanation just made it so easy. Thank you so much for this amazing series ❤

[_sk]

The way he teaches is fabulous!.... I love his enthu

[rijumondal]

He is probably one of the most genius guy I ever come across

[zeroanims]

27:58 this is a very important point to understand. I wrote the recursion slightly different from striver (i start from 0 -> N) meaning the top of my recursion is 0 and the bottom is N. So my dp bottom up nested loop is from n-1 going to 0, and will return dp[0[[k], it should still work
code:
bool dpWay(int n, int k, vector<int>& arr){
vector<vector<bool>> dp(n+1, vector<bool>(k+1, false));
for (int i = 0; i <= n; i++) dp[i][0] = true;

for (int i = n-1; i >= 0; i--){
for (int j = 1; j <= k; j++){
bool skip = dp[i+1][j];
bool take = false;
if (j >= arr[i]) take = dp[i+1][j-arr[i]];
dp[i][j] = skip || take;
}
}
return dp[0][k];
}

bool rcMemoWay(int i, vector<int>& nums, int tar, vector<vector<int>>& memo){
if (tar == 0) return true;
if (i == nums.size()) return false;
if (memo[i][tar] != -1) return memo[i][tar];

bool skip = rcMemoWay(i+1, nums, tar, memo);
bool take = false;
if (tar >= nums[i]) take = rcMemoWay(i+1, nums, tar - nums[i], memo);
memo[i][tar] = skip || take;
return memo[i][tar];
}

[smitboraniya]

At first I thought your methos is very obvious, but as we go further in dp playlist it proves to be much stronger tool to apply for solving tough problems.

[arpitrajput]

hey! we can add one more line to reduce further looping if we get our ans
add if(dp[ind][k]==true)return true;
at before end of second loop try it.


vector<vector<bool>> dp(n, vector<bool>(k+1, false));

for(int i=0;i<n;i++)
dp[i][0] = true;
if(arr[0] <= k)
if(arr[0]<=k)dp[0][arr[0]] = true;

for(int ind=1;ind<n;ind++){
for(int
bool notTake = dp[ind-1][target];
bool take = false;

if(arr[ind]<=target)
take = dp[ind-1][target - arr[ind]];


dp[ind][target] = notTake || take;
}
if(dp[ind][k]==true)return true;

}
return dp[n-1][k];

[kranjith]

Understood, Very well explained. the best DP playlist. Thanks for taking time and making the videos.

[priyanshubansal]

This is the best dp solving technique that I have ever seen. thank you for giving us this wonderful playlist