Partition Equal Subset Sum | Recursion | Memo | Tree Diagram | Leetcode 416 | codestorywithMIK

Hi Everyone, this is the 108thth video of our Playlist "Dynamic Programming (DP) : Popular Interview Problems".
Now we will be solving an very good and classic DP problem based on Knapsack - Partition Equal Subset Sum | Recursion | Memo | Tree Diagram Leetcode 416 | codestorywithMIK

In this video, we will solve it using Recursion and Memoization because I am travelling this week and got very less time today.

Problem Name : Partition Equal Subset Sum | Recursion | Memo | Tree Diagram Leetcode 416 | codestorywithMIK
Company Tags : Accolite, Amazon, Adobe, Drishti-Soft

╔═╦╗╔╦╗╔═╦═╦╦╦╦╗╔═╗
║╚╣║║║╚╣╚╣╔╣╔╣║╚╣═╣
╠╗║╚╝║║╠╗║╚╣║║║║║═╣
╚═╩══╩═╩═╩═╩╝╚╩═╩═╝

Video Summary :
Approach 1: Recursion with Memoization
This approach uses a recursive function to explore whether it's possible to form a subset with a sum equal to half of the total array sum. At each step, it decides whether to include the current element or skip it, and uses memoization to store already computed results to avoid redundant calculations. If at any point the remaining sum becomes zero, it means a valid subset is found.

Approach 2: Bottom-Up Dynamic Programming
This approach builds a 2D boolean table where each cell indicates whether a subset with a specific sum can be formed using the first few elements of the array. It starts with base cases — no elements can't form any positive sum, but sum 0 is always possible. Then, for each element and target sum, it fills the table by checking if the sum can be achieved either by including or excluding the current element. The final answer is found at the bottom-right of the table.

✨ Timelines✨
00:00 - Introduction
0:31 - Motivation
0:45 - Problem Explanation
1:36 - Thought Process
6:45 - This is nothing but Classic Subset Sum Problem
9:41 - Tree Diagram
16:48 - Coding it up

#MIK #mik #Mik
#coding #helpajobseeker #easyrecipes #leetcode #leetcodequestionandanswers #leetcodesolution #leetcodedailychallenge #leetcodequestions #leetcodechallenge #hindi #india #coding #helpajobseeker #easyrecipes #leetcode #leetcodequestionandanswers #leetcodesolution #leetcodedailychallenge #leetcodequestions #leetcodechallenge #hindi #india #hindiexplanation #hindiexplained #easyexplaination #interview#interviewtips #interviewpreparation #interview_ds_algo #hinglish #github #design #data #google #video #instagram #facebook #leetcode #computerscience #leetcodesolutions #leetcodequestionandanswers #code #learning #dsalgo #dsa #coding #programming #100daysofcode #developers #techjobs #datastructures #algorithms #webdevelopment #softwareengineering #computerscience #pythoncoding #codinglife #coderlife #javascript #datascience #leetcode #leetcodesolutions #leetcodedailychallenge #codinginterview #interviewprep #technicalinterview #interviewtips #interviewquestions #codingchallenges #interviewready #dsa #hindi #india #hindicoding #hindiprogramming #hindiexplanation #hindidevelopers #hinditech #hindilearning #helpajobseeker #jobseekers #jobsearchtips #careergoals #careerdevelopment #jobhunt #jobinterview #github #designthinking #learningtogether #growthmindset #digitalcontent #techcontent #socialmediagrowth #contentcreation #instagramreels #videomarketing #codestorywithmik #codestorywithmick #codestorywithmikc #codestorywitmik #codestorywthmik #codstorywithmik #codestorywihmik #codestorywithmiik #codeistorywithmik #codestorywithmk #codestorywitmick #codestorymik #codestorwithmik

[shubhankar]

hello bhaiya, i cracked infosys specialist programmer role (9.5 lpa) today. Got call from Training and placement cell that i got selected. I got the highest package in my entire batch. You played a major part in my journey, thanks a lot bhaiya

[coderbanda-ps]

I don't know how you manage youtube, travel and office. I appreciate your hard work man, hats off
I will soon start your dp Concetps playlist to understand how to write bottom up thank you for your efforts

[ashwin_anand_dev]

Bhaiya, you code has magic. Before watching your solution, I tried to read a couple of articles and spent around an hour on them, but could not understand the logic. Then I looked at your bottom-up approach, and on the first look, it got into my mind with ease :)

[keerthanams]

I already did the problem by own just watched the video for your motivating words

[mostlysane]

I have solved myself using tabulation approach modifying Knapsack solution.❤

[tushti]

i wonder how do you manage posting viddeos daily... its appreciation worthy and here i am struggling to solve daily challenges because of college and stuff
kudos to you!
would really love a daily routine video, it will inspire most of the people

[gui-codes]

No need to apologise sir. You are already doing enough for us even during travelling. This was easy and I was able to solve it.
Thanks to your DP Concepts playlist. When you are back, please do continue the DP Concepts playlist.

[ApadeshKumarBBB]

i am iit jodhpur student waiting for your video solution I a get it

[abhishekanand]

i have other options for POTD videos, but i wait for your video....i like your teaching very much ---- your student

[Entertainment_lock]

App bas chalte jaau share karena ka kam hum karenge ❤❤❤

[sauravchandra]

Yes, classic subset problem. Here is my C++ AC code.

class Solution {
public:
int dp[201][20001];

bool solve(int ind, int reqSum, vector<int> &nums){
if(ind == nums.size()){
return reqSum==0;
}

if(dp[ind][reqSum] != -1){
return dp[ind][reqSum];
}

if(reqSum-nums[ind] >=0 and solve(ind+1, reqSum-nums[ind], nums)){
return dp[ind][reqSum] = true;
}

return dp[ind][reqSum] = solve(ind+1, reqSum, nums);
}

bool canPartition(vector<int>& nums) {
memset(dp, -1, sizeof(dp));

int totSum = accumulate(begin(nums), end(nums), 0);

if(totSum%2==0){
return solve(0, totSum/2, nums);
}

return false;
}
};

[Anshul-qbpm]

Sir i solved it on my own, using recur +memoiz

[ranjan-gv]

I did this problem but got tle by pick and not pick thoughts process. I'm here for DP concepts!! I've already started your dp playlist

[Coder_Buzz]

Hello bhaiya first of all sorry for being inactive for last one month busy with project reviews and internship work from today onwards I'll be regular i hope u haven't forgot me love u bhaiya❤❤❤❤

[AbhishekSharma-lnwe]

Great explanation! Wish you'd gone a bit deeper into the memorization part tho. Great work nonetheless, many thanks!

[Authenticbharatiya]

sir please digit dp pe video and dp with bitmask pe please please

[vision]

bhaiya one request, please try to add tabulation approach as till memoization it feels friendly to code, but when it's the turn of tabulation, things get messed up.

[kyaHiKarSakteH]

Hello MIK, I had an online assessment today and the first problem was basically aggresive cows problems just mapped into a real world scenario but I could not identify that and I was pissed with myself. Can you like share some sort of advice, how to maybe identify or sort of extract the algorithm from the real world problem or is it Just something that will come from practice? Please reply if possible

[krishnamittal-qo]

Bhaiya plz bit manipulation ki concepts and questions playlist banao 🙏🙏

[manujsankrit]

memoization gives TLE(139/144) when using ts. Looks like I need to go for bottom up.
```typescript
function canPartition(nums: number[]): boolean {
// base check
const s = nums.reduce((a, c) => a + c, 0); // O(n)
if(s % 2 === 1)return false;

const firstSubsetSum = s / 2;
const len = nums.length;
const dp = new Map<string, boolean>(); // To save space

const solve = (i: number, sum: number): boolean => {
// base case
if(sum === firstSubsetSum)return true;
if(i >= len || sum > firstSubsetSum){
return false;
}

const key = `${i}, ${sum}`;
if(!dp.has(key)){
// main case
const take = solve(i + 1, sum + nums[i]);
const notTake = solve(i + 1, sum);
dp.set(key, take || notTake);
}
return dp.get(key);
};

return solve(0, 0);
};
```