30.) DP on subsequences

Subset sum = target✅⭐
Partition equal subset sum✅
Partition array into 2 subsets with min abs [sum(v1)-sum(v2) ]✅
Count subsets with sum k✅⭐
Count partitions with given diff✅
target sum✅

0/1 knapsack✅⭐
min coins✅---->count min coins to be taken
coin change-2--->count n(ways) of taking coins⭐✅
unbounded knapsack✅
rod cutting problem✅

-----------------------------------------------------------------------------------------------------------------------------

2 ways to generate all subsequences- Power Set, or Recursion

subset means subsequence in dsa

-----------------------------------------------------------------------------------------------------------------------------

1. Target Sum-

QUES- return true if there exists a subset with sum equal to the target in the array...

Soln assuming all array elements are positive

here f(n-1,target) will tell if there's a subsequence till n-1 index with sum = target

1.) RECURSIVE SOLN- ( time: 2^n space: N )

-----------------------------------------------------------

2. Memoized solution- ( time:- [n*target] space:- [n*target + n] )

just see which are the changing states and accordingly declare dp array and add those 2 standard lines in the recursive solution

-----------------------------------------------------

3. Tabulation- reduces auxiliary stack space of N

intitialize dp array using base cases, then make loops which are reqd as per changing states, now just copy paste and adjust the recurrence inside the loops

note- the loops ki range will be from bottom up(base case se final destination tak) in the recursion tree

---------------------------------------

4. Space optimisation-

--------------------------------------------------------------------------------------------------------------

2. Partition Equal Subsets sum-

return true if you can partition the array into two subsets such that the sum of the elements in both subsets is equal

Me- total sum nikal lo array ka aur uska half karo--> now this ques boils down to subset sum = target

--------------------------------------------------------------------------------------------------------------------------

3. Partition array into 2 subsets to minimize sum difference

BELOW SOLN ASSUMES ALL ARRAY ELEMENTS ARE POSITIVE NUMBERS

[for array containing negatives use map instead of 2d vector]

VARIATION DECODED -

target sum is total sum of array, so dp table will be filled till max possible subset sum

and now do post calculation of dp

using dp table from subset equal target problem, we can tell from each cell of the last row if we can achieve a target from 1-7 for the array from index 0 to 4....

so dp[x][y] tells if till index x we can have a subset having sum = y

we will focus on s1

s1 will be from 0 to total sum

we will use above dp table to see which are the valid sums for s1 in this range

correspondingly we will find possible s2's by subtracting sums of s1 from total sum

then we will see difference of these and then choose min😉

-----------------------------------------------------

OPTIMISATION-

we can find s1 ka sum only till target/2 kyuki uske baad dekho repeat hore s1,s2 ke pair

so for the loop which finds diff the loop can be run till target/2 instead of till target

---------------------------------------------------------------------------------------------------------------------------

4. Count subsets whose sum is k

simple count waala variation of the subset sum equal target problem, just that ek sum = 0 wala case hai naya

---------------------

Striver soln - (considering arr[i] being non zero)

recursive-

Tabulation-

Space Optimised-

for array containing 0s below is modified base case-

(considering cases like [5,7] and target being 7 or 12)

we will remove sum==0 condn as it was reducing search space in recursion tree for examples like 0,0,1 and target is 1

thus we would re think zero sum waala case

so for the 2 nested if conditions below we will return 1 or 2 and for every other cond return 0 at ind==0 wala block

----------------------------------------------

me-

-----------------------------------------------------------------------------------------------------------------------------

5. Count Partitions with Given Difference

with just a slight calculation the problem boils down to the count subset sum equal k problem

----------------------------------------------------------------------------------------------------------------------------

---------------------------------------------------------------------------------------------------------------------------

6.) 0/1 Knapsack-

since there is no uniformity between the weight and values array so greedy won't work

so we try all possible combinations and take best

state defining-

recursive soln-

tabulation-

Space optimisation into 2 arrays-

Space optimization into 1 array-
this works because for every element in the current row we need a guy from previous row with its position being somewhere in a column <=current column, so we can instead update the prev array itself but from last index to the first, kyuki agar tum j-th col pe ho toh uske aage ke cols ni chaiye tumhe j-th aur uske piche ke cols ko update krne k liye is problem mein

-----------------------------------------------------------------------------------------------------------------------------

7.) Min Coins

Given coins of different denominations and a total amount, return the minimum number of coins needed to make that amount. If it's not possible, return -1.

OPTIMIZATION PROBLEM

here greedy can't work as greedily we can sort the coins array and then always reduce the max amount using max possible biggest valued coin and then move to smaller valued coin, but consider the case-

{2,5} and amount being 11, so greedily we would take 2 coins of 5 and then we say we can't make such amount from these coins which is false since it can be made using (5*1 + 2*3 )= (5 + 6 )

so we will try all possible combinations of coins and choose that which is possible and has min coins

----------------------------------------------

ANS- major change in INF supply variation of knapsack is that in the take case we won't move

idx to idx-1

Recursive-

Tabulation-

------------------------------------------------------------------------------------------------------------------------

8.) Target sum-

count possible expressions (which simplify to target sum), which we can make by placing signs of + - in front of array elements...

Method-1: simple recursion wali approach

Method-2: this is just a variation of count partition with given difference with language of question being varied, else the solution is exactly same

---------------------------------------------------------------------------------------------------------------------------

9. Coins change-2

Given coins of different denominations and a total amount, return the number of combinations that sum up to the amount. Each coin can be used unlimited times.

COUNTING PROBLEM

here we haven't added 1 in take or not take, kyuki ek proper complete possible combination tab hi hoga jab tum last mein base case tak aa jaoge tab hi 1 ya 0 return hoga...