Partition Equal Subset Sum Leetcode 416

/*

******************* SUPER IMPORTANT *********************

https://chatgpt.com/canvas/shared/686d6b2645788191bc42b686b5773df1

*/

#include <bits/stdc++.h>

using namespace std;

// INDEX BASED APPROACH - process each element sequentially(INDIVDIUAL

// ELEMENT CHOICE DIAGRAM) TRY FILLING ALL PARTITIONS PARALLELY/AT ONCE,

// here both partitions So in base case need to compare both of them to see

// if valid path or not(equal sum)

// Generally not a good approach when you fill all the groups at once,

// because then sum of each group needs to be monitored throughout

// recursion, i.e. CHANGING,as they are INFLUENCING THE DECISION in base

// case on what to return. The sum for each partition is also NOT DERIVABLE

// at any point of time by any other variable in index based recursion

long long getEqualPartitionSum(int level, int part1, int part2, vector<int> &nums, unordered_map<string, long long> &memo){

if(level >= nums.size()){

if(part1 == part2){

return 1;

}

return 0;

}

string key = to_string(level) + '|' + to_string(part1) + '|' + to_string(part2);

if(memo.count(key) > 0){

return memo[key];

}

long long count = 0;

count += getEqualPartitionSum(level + 1, part1 + nums[level], part2, nums, memo);

count += getEqualPartitionSum(level + 1, part1, part2 + nums[level], nums, memo);

return memo[key] = count;

}

bool getEqualSumPartitionSingleGroupTracking(int index, int currSum, int &targetSum, vector<int> &nums, vector<vector<int> > &memo){

//base case

if(index >= nums.size()){

if(currSum == targetSum){

return true;

}

return false;

}

//Assert #1: currSum should never exceed targetSum

// you can assert with meaningful messages too

assert(currSum <= targetSum && "currSum exceeded targetSum");

//Assert #2: safe indexing in memo table

assert(index >= 0 && index < memo.size());

assert(currSum >= 0 && currSum < memo[0].size());

if(memo[index][currSum] != -1){

return memo[index][currSum];

}

//levels = each element

//options = whether to include in group1 or not(if not taken in group1, it already becomes a part of group2)

bool inc = false, exc = false;

//include only if does not exceed the sum limit of group

if(currSum + nums[index] <= targetSum){

inc = getEqualSumPartitionSingleGroupTracking(index + 1, currSum + nums[index], targetSum, nums, memo);

}

//exclude

exc = getEqualSumPartitionSingleGroupTracking(index + 1, currSum, targetSum, nums, memo);

return memo[index][currSum] = inc || exc;

}

//Just remember to use where N <= 20 (it is best in this range because it reduces other params in key)

bool getEqualSumPartitionSingleGroupTrackingWithMASK(int bitmask, int currSum, int &targetSum, vector<int> &nums, vector<int> &memo){

//base case

// We can't use the condition like builtin_popcount(mask) = nums.size() as we are not filling ALL the groups, As we are only filling 1 group, so some elements will be left which will logically go into the other group. So as soon as we reach the condition currSum = targetSum, that means we were able to fill that single group, so k = 0 (groups left to fill) but and used the elements required that were required to do so. So this base will suffice.

if(currSum == targetSum){

return true;

}

if(memo[bitmask] != -1){

return memo[bitmask];

}

bool partitionPossible = false;

//levels - group to filled

//options - any unused element that on being added doesn't exceed the limit(targetSum) of the current group

for(int i = 0; i < nums.size(); i++){

int elementIndexInMask = (1 << i);

int element = nums[i];

//check if element has been used or not in filling of the current or any previous group

//bitmask represents a configuration where our current element 'i' has a corresponding bit in mask (ith bit)

//We take elementIndexInMask which has all 0 bits in 31 out 32 total bits. The only bit that is set is the ith bit.

// We take '&' of these...so no matter what was present in bitmask in other 31 positions, it will become 0 as those position bits is 0 in elementIndexInMask. So the '&' would result in some non zero value only if ith bit is set in bitmask, and (1 & 1) = 1, so the resultant value would be some nonzero value. But if ith bit is OFF in bitmask(signfying that ith element has not been used yet), so it would result in 0 as ith bit of elementIndexInMask is 1 but the ith bit in bitmask 0.

if((bitmask & elementIndexInMask) == 0){

//ith element can be used in filling the group as it is unused, but using it should not exceed the sum limit of current group

if(currSum + element <= targetSum){

//unused element and not violating the sum limit

//mark the element as used

int mask = bitmask | elementIndexInMask; // will set the ith bit in the new mask

partitionPossible |= getEqualSumPartitionSingleGroupTrackingWithMASK(mask, currSum + element, targetSum, nums, memo);

}

return memo[bitmask] = partitionPossible;

}

// BESTEST APPROACH (USING BITSET AND SINGLE GROUP TRACKING) (with bitset, you can only track single group)

bool canPartition(vector<int>& nums) {

/*

USED BITSET instead of bitmask!!!

BITSET could be used only where CUMULATIVE property or CUMULATIVE EFFECT of the elements(SUM, XOR) is to be tracked instead of IDENTITY of each elements(which element, how many element, size of group etc).

It is VALUE-ACHIEVABILITY TRACKING

BITSET can be used where the VALUE that is being tracked is of order <= 1e5.

Here in this question Max Sum of a group was 10000 or 1e4.

OR

If you see large N >= 24 (Often eliminating the solution via bitmask) and CUMULATIVE PROPERTY needs to be tracked.

Only required 10001 bits in space and time complexity is also greatly reduced because it involves bit operations only.

*/

int totalSum = 0;

for(int i : nums){

totalSum += i;

}

if(totalSum % 2 != 0){

return false;

}

int targetSum = totalSum / 2;

//each bitset[i] = represents if SUM(group/partition) = i is possible or not.

//if possible, bitset[i] = 1

//if not possible, bitset[i] = 0

//So we need to maintain an bitset array of size targetSum + 1, to see if sums[targetSum] is possible or not

// bitset<targetSum + 1> sums;

//Above declaration is wrong, although we need to just maintain if targetSum + 1 is achievable or not, DYNAMIC SIZE(RUNTIME SIZE) BITSET ARRAY IS NOT POSSIBLE. IT CAN ONLY BE INITIALIZED WITH A CONSTANT.

//So to declare one, check the constraints, and calcuate what is the maximum possible sum that can be achieved .

//Here N = 200, nums[i] <= 100, So the biggest totalSum = 200 * 100 = 20000

//But We don't need a SUM(group) = 20000 sum, we just need to see if 1 group of totalSum/2 is possible or not, as the other group would automatically equal totalSum/2.

//So the max targetSum that is achievable by a group in worst case is 10000. So a BITSET of size 10001 required.

bitset<10001> sums;

//sums[24] = represents if sum(GROUP) = 24 is possible or not(we don't care about the actual element used to meet the sum criteria, we just want to know if SOMEHOW A COMBINATION OF ELEMENTS EXIST that makes a particular sum possible), here 24

//sum 0 is alaways possible, don't select any element

sums[0] = 1;

//for each element in nums, add nums to the previously achievable sums to get new sums that are possible

// (previously achievable sums + if current element added to that group) = new sum that is also achievable

//suppose previous sums that are possible for the group = 2,3,6,7 and now we have element as 5

// Now if we add 5 to all of these possible sums(much like a backtrack solution, add 5 explore that path, then add 5 to next ...), we can generate 2 + 5 = 7, 3 + 5 = 8,....11, 12

// It is simple technique,

/*

IMPORTANT

If some sums are possible using the combination of previously used elements, then

If we add the current element to all of those previously possible sums, then the new sums are also possible .

If somehow sum = 4 was achievable before, now if we the add element 5 to it(basically whatever elements help the group form the sum = 4 via any combination(we just want to know if it is POSSIBLE regardless of what element formed the group), if we add 5 in that group too, that makes sum = 9 also POSSIBLE)

suppose if the sum 4 was possible via the elements {1, 3}

Now if we add 5 in that group it becomes {1, 3, 5}, which makes the sum of group 9. So now we know that a group can be formed with sum = 9.

That is what the question demands after breaking it down to the problem where we want to know if we can form a group with sum = targetSum.

*/

for(int i : nums){

//(sums << i) shift all the previously set bits(possible sum) by position 'i'.

// basically for all sums[k] == 1, left shift those bits by 'i', saying if sums[k] = 1, i.e. sum = k is possible then a new sum, sums[k + i] = 1, sum = k + i is also possible.

//(sums << i) shifted the bit corresponding to the previously possible sum to some new bit, saying sums that can be formed by adding 'i' to all the previous sums is also possible

//Now we 'OR' it with the original BITSET sums, to update the new sums that are possible now (by adding the current element to all the previously possible sums).

// By 'OR' we maintained the previous possible sums and also updated the new possible sum.

sums = sums | (sums << i);

}

return sums[targetSum] == 1 ? true : false;

}

int main() {

// your code goes here

int n;

cin >> n;

vector<int> nums(n);

for(int i = 0; i < n; i++){

cin >> nums[i];

}

/*

NAIVE APPROACH - (INDEXED BASED, MULTIPLE GROUPS TRACKING)

// 1) Index Based Recursion (making choice for each element sequentially, valid subset formed at base case)

// 2) Tracking all groups parallely, and making decision in base case (because only there all the elements have been processed, all the elements have expressed their choices, and the sum of each partition are finalised.

//3) Memo Key = memo(index, sum1, sum2)

as index is CHANGING, INFLUENCING decision(index >= nums.size() i.e. letting us know if all the elements have been processed or not) in base case, and is NOT DERIVABLE

sum1 and sum2 are changing, INFLUENCING decision in base case(sum1 == sum2), and is NOT DERIVABLE from any other parameters

unordered_map<string, long long> memo;

cout << getEqualPartitionSum(0, 0, 0, nums, memo) << '\n';

*/

/*

// BETTER APPROACH (INDEXED BASED, SINGLE GROUP TRACKING)

// 1) Index Based Recursion

// 2) Tracking one group at a time, filling one group then the next and see if we are able to fill all the groups. If we are not able to fill a group, we backtrack to the previous groups try different combination to fill them up in hopes that it would free up the used element that can be used further down the line to succesfully fill the group that we were stuck on.

// 3) In filling one group at a time, you should know when it is completely full. So read the question again to figure out what can be the INDIVDIUAL group sum.

// 4) We want ALL the elements of array to be partitioned in 2 groups with equal sum SUM(part1) = SUM(part2)[Quesetion Constraint]

// So TOTALSUM(elements) = 2 * SUM(part1) => SUM(part1) = SUM(part2) = SUM(TOTALSUM)/2

// 3) Memo key here would be (index, currSum, k) as all 3 are CHANGING, INFLUENCING & NOT DERIVABLE

int totalSum = 0;

for(int i : nums){

totalSum += i;

}

//if the sum itself is not divisible by 2, then it is impossible to PARTITION in 2 groups

if(totalSum % 2 != 0){

cout << "NOT POSSIBLE TO PARTITION INTO 2 GROUPS OF EQUAL SUM" << '\n';

return false;

}

// It might be possible to partition, and it is only possible when both of the partition equal totalSum / 2;

int targetSum = totalSum/2;

//Clever trick - Even if you are able to partition 1 group with sum equal to totalSum/2, then the other half automatically partitions with sum = targetSum/2. So memo(index, currSum, k) => memo(index, currSum).

// We were able to remove the dependency from 'k' because instead of filling both the groups, we can just check if one of the group can achieve sum = targetSum/2.

vector<vector<int> > memo(n, vector<int>(targetSum + 1, -1));

//************IMPORTANT

//assert is a powerful tool to check if some logical condition is true or not while code is getting executed

//Used as safe access to index (both level param/recursion driving param such as index or level and memo table declaration)

//Use it before or after a risky/sensitive array access

//Assert #1: memo size should always be these dimensions

assert(memo.size() == n && "memo table should be of size n");

assert(memo[0].size() == targetSum + 1);

cout << boolalpha << getEqualSumPartitionSingleGroupTracking(0, 0, targetSum, nums, memo) << '\n';

*/

/*

//BEST APPROACH - (MASK BASED, SINGLE GROUP TRACKING)

//1) Use mask instead of index, mask configuration represents a VALID COMPLETE SINGULAR PATH IN CHOICE TREE DIAGRAM or SUBSET OF CHOICES EXPRESSED BY ALL THE ELEMENTS

//2) //Unlike index based recursion, where all the elements are processed at the base case/leaf node of the recursion tree, we are only able to the full choice diagram at base case. But in MASK for N elements, a particular state of mask (0th bit to N - 1th bit) , represents the whole choice. We recurse with mask, and a MASK at any STATE OR TIME fully REPRESENTS A VALID CHOICE made by all the elements out of 2^N choices. We don't need to wait for the base case to see what were the choices made by the elements.

Think of it as - mask from (0th bit to N - 1th bit, every bit is going to be either 0 or 1 in this range, some bits in this range are 0 and some of them are 1). Those which are 1, are the elements which decided to COME in the subset, those which are 0, decided NOT TO COME in the subset.

****** IMPORTANT

The CONFIGURATION of MASK at any point of time represents a choice out of all the 2^N different choices that can be formed by N elements

******** VERY IMPORTANT

SINGLE GROUP TRACKING is the staple, we will do it with index based as well as mask based recursion.

It reduces the time complexity as well as the space by not tracking multiple groups at once and having to linearize multiple values to form a key and do memoisation.

It reduces the space because we are only tracking 1 group sum at a time and checking if it equals to some targetSum. So our memo key instead of looking like

memo(mask, sum1, sum2,.....sum k) it looks like memo(mask, currSum, k), where currSum represents the sum of the current group getting filled and k represents the number of groups left to filled.

So no matter how many group we have to fill, we can always maintain it with 2 variables,

currSum & K.

But in multiple group tracking we have to monitor all the K groups at once making the number of keys directly dependent on K.

So as K increases, length of memo key also increases memo(sum1, sum2.....sum3) as we have to maintain all k groups together.

So SINGLE GROUP TRACKING makes sure we can always track any number of groups with just 2 variables, instead of K variables in multiple groups

Mask helps by reducing the number of variables further, because mask at any moment stores the whole information about the CONFIGURATION, and we can deduce of lot of things from that configuration such as sum, size etc.

So in index based recursion key would look like memo(index, currSum, k). All 3 are CHANGING, INFLUENCING and NOT DERIVABLE from any parameter, because index does not remember any configuration state so far, it only represents where we are are and how much we need to go further to reach base case.

But this is where mask shines, as mask represents the COMPLETE SINGULAR PATH IN INDIVDIUAL ELEMENT CHOICE DIAGRAM, it represents a VALID SUBSET formed by choices made by ALL THE ELEMENTS, unlike index which just tells that we have processed/made decision TILL ith index and we still need to reach base case where WE CAN MAKE DECISION based on some other parameter that we are maintaining in our recursion state (such as currSum and k to make a decision in base case) because from index alone we cannnot derive currSum or k, IT JUST TELLS WHERE YOU ARE, NOT WHAT YOU ARE

With index based recursion, key was memo(index, currSum, k) but with mask this reduces to memo(mask), as the other 2 can be derived from mask.

SUMOFSETBITSELEMENTS(mask) / targetSum = NUMBER OF VALID GROUPS FORMED, which is what k is

SUMOFSETBITSELEMENTS(mask) % targetSum = The PORTION OF SUMOFSETBITSELEMENTS(mask) that has not been used to fill any previous VALID GROUP, but it is getting accumulated in the current group getting filled, essentially telling how much full the current group is, or what is the currSum

So K and currSum will be used in recursion just to drive it (help writing conditional or help in decision making in base case) but it would be treated as RECURSIVE SCAFFOLDING.

As mask can derive the other 2 at any point of time, there is no need to memoise them, which means no matter which path we take to reach 2 different states, if their mask is same, the other 2 params would also be same for those states. It does not need specification based on params that can be derived. So -

R1 (mask, a1, b1) and R2(mask, a2, b2).

as we can see R1 and R2, both states have the same mask, so a1 = a2 = f(mask) & b1 = b2 = f(mask)

So a1 = a2 and b1 = b2 at any state where mask1 = mask2 .

*/

/*

SINGLE GROUP TRACKING (SGT) is better than multi-group tracking because:

- In multi-group tracking, we need to track sum1, sum2, ..., sumK → O(k)-sized memo keys.

- As k increases, memo size increases exponentially.

In contrast, SGT fills one group at a time. When a group reaches `targetSum`, we move to the next group.

- Memo key reduces to: (currSum, k) → only 2 parameters, regardless of how many groups we track.

*/

/*

============================================

🔍 MASK vs INDEX — SINGLE GROUP TRACKING DP

============================================

🎯 Goal: Fill one group at a time (say group1), each of size `targetSum`.

If we can successfully fill `k` such groups.

===========================================================

✅ INDEX-BASED DP: memo(index, currSum, k) — WHY IT WORKS

===========================================================

- `index` = position in array => tells us how many elements have been *processed*

- `currSum` = sum of elements added to current group

- `k` = how many groups are still left to fill

- This state tracks:

• Which elements are *considered* (via index)

• How much we have *filled* in current group (currSum)

• How many groups we *still need* to fill (k)

❗ BUT `index` itself doesn't track which elements were actually *included* or *excluded*

➤ So we can't derive currSum or k from index alone

➤ Every parameter must be explicitly passed and memoized

➤ Total states: O(N * targetSum * k) → large memo

======================================================================

✅ MASK-BASED DP: memo(mask) — WHY IT’S OFTEN SUPERIOR FOR N <= 24

======================================================================

- `mask` = bitmask where i-th bit is 1 if nums[i] is already used in any group

• For N = 4 → mask = 0b1101 means nums[0], nums[2], nums[3] are used

✅ ADVANTAGE: Full configuration is captured by mask → we can DERIVE:

• `currSum` = sum of all elements in current partial group

= total sum of used elements % targetSum

• `k` = how many *full* groups formed

= total sum of used elements / targetSum

So:

• State is fully determined by `mask`

• No need to track or memoize currSum or k separately

🎯 Result: memo(mask) is sufficient!

➤ Saves space: O(2^N)

➤ Reduces overlapping subproblems (merges many (currSum, k) into 1 mask)

➤ Faster lookups with integer keys (if using vector or unordered_map)

=====================================================================

⚠ LIMITATION OF MASK METHOD — USE ONLY WHEN N ≤ 24

=====================================================================

- There are 2^N different masks for N elements

- At N = 24 → 2^24 ≈ 16.7 million states → typically acceptable

- At N > 24 → 2^N becomes too large to store/compute efficiently

✅ Summary:

• For small N (≤ 24), mask-based DP is often more efficient and elegant

• For large N and SMALLER SUM, prefer index-based DP (memo(index, currSum)), which runs in O(N * targetSum)

🧠 PRO TIP:

Use `mask` when:

• You need to track *subset usage*

• You can derive all needed parameters from it (e.g., sum, size, group count)

Use `index` when:

• You need sequential decisions (e.g., combinations, fixed order)

• You care about positions, not configurations

Example:

Index DP : memo(index, currSum) → O(N * targetSum)

Mask DP : memo(mask) → O(2^N)

*/

int totalSum = 0;

for(int i : nums){

totalSum += i;

}

if(totalSum % 2 != 0){

cout << "NOT POSSIBLE TO PARTITION INTO 2 GROUPS OF EQUAL SUM" << '\n';

return false;

}

int targetSum = totalSum/2;

//here we don't need to maintain k, as there are only 2 groups. So just fill 1 group with sum = targetSum, other group would automatically equal targetSum.

//SIZE OF MEMO ?

// RANGE(MASK) => mask represents a configuration in the FORM OF AN INTEGER, i.e. each bit represents the choice of an element. There are N elements, so N bits needed. 0th bit to (N - 1)th bit. A configuration is flipping of bits between that range.

//N bits are need, so we left shift 1 by n, to acquire N bits.

vector<int> memo((1 << n), -1);

//IF there N bits in consideration - what is the minimum value and the maximum value that mask can take

//The integer value of mask, represents a valid configuration where some bits are on of off.

// such as mask = 3 represents 0b011 or mask = 10 = 0b1010

// min(mask) = 0b00000 = all N bits OFF = no element taken

//max(mask) = 0b11111....N times = all N bits ON = each element taken

cout << getEqualSumPartitionSingleGroupTrackingWithMASK(0, 0, targetSum, nums, memo) << '\n';

}