Dp 16. Partition A Set Into Two Subsets With Minimum Absolute Sum Difference | DP on Subsequences

[@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. Keeping a like target of 500 ❤✌🏼

[@divyaporwal589]

It is not working with negative numbers, for example the array is -36,36 and then the target is zero

[@harshitrawat138]

@@divyaporwal589 Dp requires array and array can't have negative indexes. If array contains negative numbers you can subtract the most negative number of given array (minx) from every element array so the all the elements will be positive.

[@spytonic4171]

@@harshitrawat138 truee but the problems comes when there is a random so if we check for negetive numbers at starting and find diff with each number the we can return it other wise we can continue this algo nice idea

[@kaushalwaghela429]

understood if possible, please give leetcode and gfg problem links also. thanks :)

[@trendtoyou7967]

We need not calculate minimum repeatedly. Traverse last row in dp array in reverse order and return first true cell.... Total-2*i

[@aryashjain7893]

understood, but the leetcode question mentioned in the sheet requires meet in the middle approach as it has got negative values, and tabulation fails in this case.

[@ankitanand1539]

Use long long

[@fettuccine794]

Exactly !!!

[@dhananjaygorain6375]

@@ankitanand1539 still it showing runtime error can you give your code please

[@gamersgame43]

use unordered_set?

[@ganishk3568]

@aryadhjain7893 that is not an issue if you have initial offset of 10⁷. But the problem is requires both the partitions should be of equal size.

[@rishabhsinha7250]

This is the first time when I am able to understand what a DP table looks like in real and how it works. Its a level up for me. ThankU Striver.

[@vikasbagri1225]

Understood it very well Thanks for this amazing series You really are contributing a lot to this community Best DP series in the whole youtube

[@visheshagrawal8676]

it took me 50 mins to solve the question without looking the answer it's all because of you the way you teach.. ✨✨✨✨

[@mrsunny8299]

understood, i dont know why i was skipping dp, it is easy, (you made it easy to understand this). Thankyou.

[@pratikdas1780]

I could do the memoized version on my own, but could never do it the bottom-up way. today, i can say that it's clear. and it was damn simple. just checking the sums my array of size n can produce. amazing insight.

[@vikasgupta6701]

Able to solve this problem without seeing the video and using concepts learned in past two videos. That's the power of striver's lectures. Thanks!!

[@tonyconor681]

exactly

[@pritimurmu7898]

bro how did you solve for negetives

[@prashantpal3510]

me too

[@VedeshPadal-ev9tt]

@@pritimurmu7898 were you able to solve this question on leetcode

[@SahanaaEvan-mo6zv]

Understood! Striver you are just brilliant. Your explanation and these concepts are blowing my mind off! Damn I got lucky coz i found a teacher like you! Thank you so much!

[@rohitbadhai8219]

We can optimize space complexity here since maximum value a subset can take for minimum absolute difference is total_sum/2 so we can make 2d vector for total_sum/2 instead of total_sum and then iterate last row of vector from last col and the first cell with true will be subset1.

[@sakshisakshi5677]

You made the concept clear easily and smoothly🙌

[@shreyashtech8556]

Dude, really thankful to you man. I solved this question and 95% of the previous questions on my own. the reason is you. your explanation is out of the world. thanx again. hope we meet in person in the near future.

[@sanginigupta1312]

Was able to solve this in a single go, thank you striver bhaiya, only because of these videos I'm able to develop an intuition in DP problems

[@stith_pragya]

UNDERSTOOD............Thank You So Much for this wonderful video........🙏🏻🙏🏻🙏🏻🙏🏻🙏🏻🙏🏻

[@iamnoob7593]

man i just dont understand how is he able to do video recording at freakin 4 AM in the morning , Very few match that level of hardwork.

[@VY-zt3ph]

This is the question which I was eagerly waiting for you to upload since the day you uploaded first DP lecture in this playlist.

[@anshul5533]

Striver bhaiya i think it can be further optimized in terms of time and space if we take our sum as sum/2 initially (as we have taken in DP-15), then the TC : N * (k/2) and SC : (k/2) because we are just bothered about S1 till k/2

[@takeUforward]

True.. concept clear hone se u urself can do these small things :P

[@sparks8754]

Inspiring

[@deepaksarvepalli2344]

I am searching for this comment... satisfied...😂

[@vanshsehgal9475]

Can you explain a lit bit more? I did not clearly get what are you trying to say..

[@abhishekcs5468]

@@vanshsehgal9475 You basically try to find target as upperbound of sum/2 and optimize for closest. Here is the memoized solution without space optimization. --------------------------------------------------------------------------------------------------------------------------- int dfs(int ind, int upperBound, vector& nums, vector& dp){ if(ind > nums.size() - 1) return 0; if(dp[ind][upperBound] != -1) return dp[ind][upperBound]; int notTaken = dfs(ind + 1, upperBound, nums, dp); int taken = -1e8; if(nums[ind]

[@nikhilprasad644]

bro this problem work only for +ve numbers and not on negative numbers. pls do make a follow up for negative numbers as well, as it might come up in an interview. good companies do ask such. thanks

[@SuryanshKumarPathak-m8o]

Did you come across a solution for the negative numbers?

[@EerieEntertainment-mc4ce]

@@SuryanshKumarPathak-m8o agar array ka minimum element negative hai to saare element me use add krke array ko non negative banalo

[@manikiran949]

Hey did you find a dp solution for negative numbers ? , I have seen in leetcode that it is unsolvable with dp for negative numbers .Thanks

[@ramakrishnan4356]

Instead of storing in array store the same in map create map where you can store corresponding sum for values this way we can handle negatives also

[@safiwasif2905]

@@ramakrishnan4356 thx mate

[@mohan_codes]

Amazing! thankyou DSA parasurama striver best teacher ever in my life.

[@pritikasharma9857]

Amazingly explained!. But I had a doubt won't this method fail if we have negative elements in the given array ? Could you explain this too

[@amritanand1714]

Yeah it's a problem. I think we cannot solve then through this way. There are questions on leetcode with negative values. Anyone please reply if they have any solution for this?

[@channelname4394]

Best explanation. understood , hope this channel reaches more people

[@AquaRegia-i3u]

Quick Tip 💡: If you want to solve this using memoization, you need to make sure that you call the recursive function for all possible targets. For example let the sum = 10, so target = 5. Now if you call function for 5 i.e. F(n,5) it may not always fill the complete dp grid. So you have to call all F(n,5) F(n,4) .... F(n,0) to make sure all dp[i][j] are filled. This won't affect the time complexity as if it was previously calculated it won't be calculated again due to memoization. In tabulation we go from 0 -> n, filling all dp[i][j] no matter what, so in that case it all indexes are filled.

[@kishorkumarbehera5412]

Can you give me the code for reference ?

[@AquaRegia-i3u]

public class Solution { public static int minSubsetSumDifference(int[] arr, int n) { int sum = 0; for(int num : arr) sum += num; int k = sum/2; if(n==1) return arr[0]; if(k==0) return 0; Boolean[][] dp = new Boolean[n][k+1]; for(int i=k; i>=0; i--) find(arr, i, n-1, dp); for(int i=k; i>=0; i--){ if(dp[n-1][i]!=null && dp[n-1][i]) return sum - (2*i); } return -1; } private static boolean find(int[] arr, int k, int i, Boolean[][] dp){ if(k==0) return true; if(i

[@AquaRegia-i3u]

@@kishorkumarbehera5412 added the code

[@kishorkumarbehera5412]

@@AquaRegia-i3u Instead of calling for each target we can call it for sum/2. So when we are picking and not picking we have the sum of the subset, so we can store the difference between the subset sum and the target which is total sum/2, and taking minimum of all subsets. So when returning the final answer we should check if the total sum is even or odd. Accordingly the answer would be 2*ans or 2*ans+1.

[@RohitKumar-jd7un]

code for this approach bool helper(int ind,int k,vector &arr,vector &dp) { if(k==0) { return true; } if(ind==0) { if(arr[ind]==k) { return true; } else return false; } if(dp[ind][k]!=-1) { return dp[ind][k]; } bool nottake=helper(ind-1,k,arr,dp); bool take=false; if(arr[ind]

[@MohammedAmrath]

Bhayya can you explain how can we handle the negetive cases where -10^7

[@dennyage4791]

What if we have negative integers in an array, then this approach won't work ??

[@jaycodes6599]

In tabulation there is no need of this condition : arr[0] = 0 Therefore a[0] will be always less than or equal to k

[@paridhijain7062]

Understood. Sir, You are really making great efforts for students like us. Thank you for teaching us.

[@codelikebeast3971]

Awesome Striver , I was confused in how dp vector is formed step by step and what does it signifies, you cleared it with so much clearity . Respect

[@iamnoob7593]

same i had doubt too abt it now its clear.

[@shivamdwivedi8120]

In case of negative integers, what should we can do ?

[@VishalGupta-jh9nz]

Just add absolute value of minimum integer to every element

[@avicr4727]

@@VishalGupta-jh9nz can you provide me the code it will be very helpful

[@VishalGupta-jh9nz]

@@avicr4727 Yes, I can provide but it gives TLE class Solution { public: int f(int ind, int target, int sum, int size,vector& nums, int n,vector&dp ){ if(ind==-1 && size==n/2){ return abs(target-2*sum); } if(ind==-1 || size>n/2){ return 1e8; } if(dp[sum][size]!=-1)return dp[sum][size]; int notTake = f(ind-1,target,sum,size,nums,n,dp); int take = f(ind-1,target,sum+nums[ind],size+1,nums,n,dp); return dp[sum][size] = min(take,notTake); } int minimumDifference(vector& nums) { int n = nums.size(); int mini = 0; for(int i=0;i

[@yogeshlamba5485]

@@VishalGupta-jh9nz Consider an array , arr = [-1e7, 4, 7, 1e8, 6] The minimum number here is -1e7, and if go for adding this to all elements, adding it to 1e8 will be out of INT_MAX.

[@keshavbaheti7327]

​@@yogeshlamba5485 use long long and guess what 1e7 +1e8 is not equal to 1e9.😊

[@cyro_-ej6xm]

kudos striver, you are the reason i got my confidence back , thanku so much , appreciate all the hard work you do , it changes life of thousands .

[@udaypratapsingh8923]

you made the concept clear easily and smoothly🙌 : )

[@kushalgupta2041]

An another apporach can be:- We just have to fix the target to the (totalSum/2) and return the minimum difference between the nearest value to the target for example the target we need is 5 and if there exist a sum of 5 then we return 0 means the target is possible and if there exist the closes value nearest to the 5 is 3 then we return 2. Here's my code hope you understand what i did:- int f(int idx, int target, vector &dp, vector &nums){ if(target == 0) return target; if(idx < 0) return target; if(dp[idx][target] != -1) return dp[idx][target]; int notPick = f(idx - 1, target, dp, nums); int pick = 1e9; if(target >= nums[idx]){ pick = f(idx - 1, target - nums[idx], dp, nums); } return dp[idx][target] = min(pick, notPick); } int minSubsetSumDifference(vector& arr, int n) { int sum = 0; for(int i = 0; i < n; i++) sum += arr[i]; vector dp(n, vector(sum / 2 + 1, -1)); int minLeftSum = sum/2 - f(n-1, sum/2, dp, arr); int minRightSum = sum - minLeftSum; return abs(minLeftSum - minRightSum); }

[@prajjwalpandey2278]

This can be alternatively solved, if we can find a subsequence with sum closest to totalSum/2. Correct me if I'm wrong.

[@vedanshbhardwaj6548]

ya even I did so, but somehow the space optimised solution went wrong

[@amitmahato6404]

[2,3,7], sum/2=6, closest sum can be 5 or 7

[@vedanshbhardwaj6548]

@@amitmahato6404 ya but the catch is we will only check till totalSum/2....because if one is say 5, other is bound to be 7 so why check for anything greater than the totalSum/2

[@amitmahato6404]

@@vedanshbhardwaj6548 yeh, S1=5, SO S2 WILL BE 7, MIN DIFF IS 2

[@JeevanGaikwad-G1]

Understood. Very nicely explained the tough problem in an elegant way. Thanks.

[@aryanbhagat6252]

How do we do this with negative elements as well?

[@kotipallimadhumeher71]

Understood bhaiya!! In short we can say that the dp table last row defines whether the target value is possible from given array or not.Then all possible target values are derived from the dp table and we can take min diff among the all abs diff.

[@amritanshusinha9401]

Hey bro! Great video and explanation! Just had a small question. How would you approach a similar problem where the sizes of both the partitioned subsets must be equal?

[@rishabhgupta9846]

understood,able to solve by my own .What I was doing is calling memoization for every subset sum s1 which is giving me TLE. But using tabulation we don't need to call memoization again and again and can solve in one go

[@bapanmandal9019]

In case of negative integers, what should we can do ,vaiya ?

[@HarshKumar-ip5nr]

substract min(nums.begin(), nums.end()) from each element.

[@MukeshKumar-cc3uh]

Understood ❤ and thanks for the inspiration by working at 4AM in the morning.

[@guptashashwat]

If array elements are negative what should we do?

[@denishfuletra7863]

let me know if you find ans for negative elements.

[@himanshujindal1532]

I appreciate the hardwork you putting

[@alessandrocamilleri1239]

Great video. I simplified the minimum subset difference as follows: int i = totSum / 2; while (!dp[i]) i- -; // will not go out of bounds since i always stops at dp[0] which is always true return (totSum - i) - i;

[@ishaanchandak4774]

i found this one a bit harder than the previous ones but gave time watching video and doing it by myself and understood it . great work man . n

[@shantanu240895]

How would you handle this problem in case the numbers in an array are negative or zero too? The tabulation wouldn't work in such a scenario.

[@sherlockholmes1605]

It would right? if we add an extra check to see if the index is going out of bounds for dp[i-1]th row.

[@ihsannuruliman3656]

it would work yeah just check of out of bounds.

[@SR-we1vl]

Can you please share the code!

[@tusharnain6652]

It wont work with negatives, there's a negative number case in leetcode, this solution fails there.

[@jigardoshi2852]

Yes agreed, this DP solution will not work when numbers are negative or 0 or for matter if totalSum of all nums is 0.

[@deepanshurohilla2114]

Can we do it using Memoization techniqe of parent problem "Subset with given Sum"?? The answer is no because recursive technique always fills the cells in the table which are neccessary for solving the bigger problem, it will not always fill the whole matrix but here we need the whole (n-1)th row to be filled to do partitioning hence we can do it using tabulation only. Below is the code using pick and notPick technique very easy to understand : #define vi vector class Solution{ public: // Subset with given sum bool subsetToSumK( int n , int k, int arr[], vector &dp ){ for( int i=0; i

[@krishan_aggarwal9376]

Please make a video regarding neagtive values too 😓. This one understood❤❤

[@harshvardhangupta5323]

wont it be the same logic?

[@sumerrawat6947]

@@harshvardhangupta5323 dp cannot store negetive indexes

[@surajbaranwal56.]

leetcode qn

[@rickk3300]

I also have this same doubt

[@cooltomcatty]

Beautiful Explanation!!! Kudos!!

[@nitishverma1484]

Its a suggestion, If you could explain the need of the array as you explained it in this video , in DP-14 video , as I was very confused as to what those T/F represent till end. Now it gets cleared here. I have traced the whole array for that and also that arr[0]

[@amartyagupta9922]

arr[0]

[@ObitoXuchiha942]

We can have only sum/2+1 columns in our DP array. It also worked else it was giving TLE for 1 case. Love this playlist ❤❤

[@himansh4812]

Yes. Only columns till totalsum/2 is required.

[@meerapanchal8258]

For those who are having 49/50 testcase passing on coding ninjas iterate the inner loop upto target/2 and while calculating minimum absolute difference, iterate loop from target/2 to 0 and as soon as you get first true value break the loop (maximum the target value when dp[n-1][target] is true , minimum the absolute difference)

[@neelulalchandani7429]

thanks this helped.

[@parasjaggi268]

understood i tried earlier i made recursion but wasn't able to make it to dp ,,,,,,,,,thanks for making it easy

[@vinayprakash1687]

Thanks. I feel if I got this question without knowing about previous question (partition equal subset sum), I would solve it differently. 1. Set target = sum(arr)// 2 2. Try to subtract all the array elements such that the target becomes 0 or atleast the distance from 0 is minimum. In other words, try to find maximum sum using the elements such that it is

[@advaitbajaj4241]

Even I thought of the same way but am unable to code it this way. Could you please provide me the code?

[@hemasaijammana5658]

This is the same question I was asked in yesterday's interview. I came with recursive and then tried of memoization. After memoization it is giving me TLE, now I am watching this video

[@pawanagrawal7653]

in which company..?

[@spytonic4171]

do you use recursion??

[@SuryanshKumarPathak-m8o]

As always, great video. Thanks for the explanation Striver. Two points - 1. Rather than finding minimum for every single element, we can run a loop starting from the middle element till 0, and return the first value where dp[n-1][i] == true. 2. How can a problem be solved where the array can contain negative numbers?

[@sumitkumartah2106]

just sort the array

[@adi_7861]

How we can make it work if array contains negative elements as well?

[@anshumansharma2251]

meet in the middle or binary search

[@gnanaphanideep6398]

understood! Thank you for the explanation.

[@sannareddymonesh7598]

This problem is entirely depending upon the total sum of array . What if the total sum of array is negative. Then we cannot create negative size dp array

[@balakrishnanr648]

in LC its that way

[@softwarefoodiee]

Sum cannot be negative sunce its mentioned that all the elements are non-negative.

[@surya4193]

thanks striver,I am able to improve my coding skills the main reason is you and your way of teaching

[@Pavankumar-ck5ot]

Understood. I think if we declare dp array of size [n][total sum/2+1] will also work.

[@takeUforward]

Yes works

[@ntgrn-pr5yx]

understood , thank you striver

[@prateeksharma3698]

If negative elements are also present in given array then what will be maxSum ?

[@sageoustheory1957]

did u find the ans ?

[@hrithikm.6619]

Slightly different logic where I'm directly trying to find the subset having the sum as close as possible to sum/2. #include int recursion(int ind, int target, vector& arr,vector &mem) { if(target == 0) return 0; if(ind < 0) return target; if(mem[ind][target] != -1) return mem[ind][target]; int not_pick = recursion(ind-1,target,arr,mem); int pick = INT_MAX; if(target >= arr[ind]) pick = recursion(ind-1,target-arr[ind],arr,mem); return mem[ind][target] = min(pick,not_pick); } int minSubsetSumDifference(vector& arr, int n) { //taking the total_sum int sum = 0; for(auto it : arr) sum+= it; vector mem(n,vector(sum/2 + 2,-1)); //memoization int call = 0; if(sum%2 == 0) { call = recursion(n-1,sum/2,arr,mem); return 2*call; } else { call = recursion(n - 1, (sum / 2) + 1, arr,mem); return abs((2 * call) - 1); } }

[@ShubhamKumar-vp4pu]

Hey striver, I have understood the concept but can we solve it using recursion ?

[@sjsjdsbsjjwjs2659]

public class Solution { public static int minSubsetSumDifference(int[] nums, int n) { // Write your code here. int sum=0; for(int x:nums) sum+=x; int res=Integer.MAX_VALUE; for(int i=0;i

[@prakharsoni7621]

Yes by adding this... for(int i=s;i>=0;i--) f(dp,n-1,i,arr); Your dp Array now fill perform the operation now :)

[@harisrashid0773]

yes we can but will give tle ;

[@pranchalsharma2647]

We need to look at the constraints here because this only works for positive integer array and not when negative numbers are in the array.

[@PANKAJKUMAR-oy1hh]

i solved by finding value closer or equal to the half of total sum. but, i feel ur approach is more clear and concise.

[@sameerbilla515]

I did same, but cannot memoize it.. can you please tell how can I memoize it

[@rohankar5604]

Understood, great explanation !!!

[@maneeshapanu]

This code now is giving tle with one test case.

[@vedantojha766]

Yes

[@chanchalroy3417]

Just because of the previous lectures I was able to solve this problem without watching this lecture. Take a bow... Understood ❤

[@jeet7000]

here's my recursive solution class Solution{ public: int ans=1e8; int solve(int i,int arr[],int sum,int curr,int n,vector& dp){ if(i==n){ ans=min(ans,abs(curr-sum)); return ans; } if(sum

[@shadab9764]

Thanks man!

[@superiors2817]

Hi sir, your explanation of this problem was excellent. But I am facing a problem. In your updated DSA sheet, the given problem link is of leetcode. There, there are different constraints (basically negative numbers). Kindly also explain how to handle negative numbers (since negative indices are not possible, hence this solution won't work)

[@shashanksinghal8395]

We don’t need to fill the complete dp table up to totsum, we can fill up to totsum/2. It will be much more efficient

[@hashcodez757]

"UNDERSTOOD BHAIYA!!"

[@vinaykumarratnala5832]

I have solved this question before watching this video only based on the concepts applied in all prev videos. thank you so much

[@Swiftie13498]

Understood !This series is just insane.I've never understood dp this much easily.Striver you are god level person.Period.

[@rahulgyawali]

Great Explaination! What if array contains negative numbers? Store indexing can be challenging.

[@gouravkrroy3625]

The same problem with sorted array becomes book allocation problem?.....if yes then the tc would be nlogn+nlogn and space would be o(1)?....just random thought ! Correct me please if wrong!

[@chamanjain9843]

28:22 line no 9 if(arr[0]

[@shauryatomer1058]

thanks again for this awesome tutorial

[@likithgullapudi2275]

used hashing(to store decimal values ) used normal recursion approach from typing import List def minSubsetSumDifference(arr: List[str], n: int) -> int: def fun(i,j): if (i,j) in temp: return temp[(i,j)] if j=0: return min(j,j-arr[0]) else: return j notake=fun(i-1,j) if arr[i]

[@likithgullapudi2275]

made sum to even numbers so that we can do normlaly from typing import List def minSubsetSumDifference(arr: List[str], n: int) -> int: for i in range(len(arr)): arr[i]=2*arr[i] temp=[[-1 for i in range(sum(arr)+1)] for _ in range(len(arr)+1)] #print(temp) def fun(i,j): #print(i,j) if temp[i][j]!=-1: return temp[i][j] if j=0: return min(j,j-arr[0]) else: return j notake=fun(i-1,j) if arr[i]

[@tanazshaik678]

2 mins of silence for how my brain just stopped in shock when solved this hard problem in a way that my mind processed.

[@HarshKumar-ip5nr]

Meet in the middle approach is needed for solving this question on LeetCode. I did every thing but ultimately had to switch to that. Reason being, the leetcode question asked to divide the array into two equal parts, so can't be done using dp. Anyway the code till here is: class Solution { private: long long min(long long a, int b){ if(a>b)return b; return a; } long long minl(long long a, long long b){ if(a>b)return b; return a; } public: int minimumDifference(vector& arr) { long long n = arr.size(); long long mini=INT_MAX; long long totSum=0; for (long long i = 0; i < n; i++) { mini=min(mini, arr[i]); } for (long long i = 0; i < n; i++) { arr[i]-=mini; } for (long long i = 0; i < n; i++) { totSum += arr[i]; } vector < bool > prev(totSum + 1, false); prev[0] = true; if (arr[0] cur(totSum + 1, false); cur[0] = true; for (long long target = 1; target

[@dank7044]

It can be done by DP but i will give TLE.

[@BhaskarDev-ll8hv]

this will work only for all positive elements or negative elements for mixture of both an algorithm called "meet in the middle" will be used

[@_ArjitKhare]

Amazing Turned a question into a tool

[@harshpratapsingh1638]

you really make this question a piece of cake

[@Rahul-ls4ju]

Understood. Another approach which I thought was to find S1 such that it is nearest to totalsum/2. THis could be done by map or simply by loop. Then could find S2 and hence S2-S1

[@riyakumari8377]

i thought of same but cant code it properly! :(

[@xyz956]

​@@riyakumari8377 int rec(vector &arr, vector &bucket, int index, int sum) { if (bucket.size() == arr.size()/2) { // for ( int i =0 ; i

[@daniyalhussain5231]

Why cannot I think of such solutions LoL!!!! Amazing Job!!!

[@jaydevkundu554]

Able to solve with just starting hints of 5min.. Thank you striver.. ❣

[@atmaramkambli7800]

1st half of video, I was like why we're learning subset equal to k tabulation, 2nd half of video, I am saying "The Legend Striver"

[@prabhakaran5542]

Understood ❤

[@shubhambalodhi6485]

similar question leetcode 1049 -> last stone weight II

[@rutwikmore7462]

Explained beautifully ♥

[@sangeethagopalan301]

Greatly simplified!! Understood!!!!

[@madhurgupta4220]

Very Good Explanation. Understood. I think this will be more than enough

[@sooyashjaju4208]

Very much Intuitive ✨

[@lol_iris237]

for java, convert the string to char array instead of using .charAt, the code will be 3 times faster

[@parthsalat]

Understood Kaka! Enjoy your stay at Warsaw!

[@rishabhbajpai6234]

understood ..........thanks for doing gret work sir

[@abhishekjhanji3014]

"Understood" ....Guess what I coded this problem with a different approach and my score is 100 in this problem of """DP""" ....It's amazing to solve DP ..Thanks bhaiya .... My code here using memoization.. int findans(int a,int t_sum,vector&arr,int i,int &min_v,vector&dp){ if(i

[@AmanKumar-fl5ws]

was looking for this !!

[@the_duskyindiangirl]

This approach fails when you have negative numbers in index 0. prev[arr[0]] = true throws index out of bound exception when arr is [-36, 36]. This is a leetcode test case.

[@mohitsingal6567]

you can improve it in target loop we are running it till k (total sum) but in s1 loop we are running it till k/2 we know that k is acheivable but are goal is not to find k acheivabe or not we only need it till half way so we run the target loop till half(k/2) since it is going to repeat hope u understood and guys worry not just keep working dp is tricky it will take some time just dont leave

[@paveshkanungo6338]

Understood! Thank you Striver