Register for our webinar

### How to Nail your next Technical Interview

1 hour
1
Enter details
2
Select webinar slot
*Invalid Name
*Invalid Name
Step 1
Step 2
Congratulations!
You have registered for our webinar
Oops! Something went wrong while submitting the form.
1
Enter details
2
Select webinar slot
*All webinar slots are in the Asia/Kolkata timezone
Step 1
Step 2
Confirmed
You are scheduled with Interview Kickstart.
Redirecting...
Oops! Something went wrong while submitting the form.

## You may be missing out on a 66.5% salary hike*

### Nick Camilleri

Head of Career Skills Development & Coaching
*Based on past data of successful IK students
Help us know you better!

## How many years of coding experience do you have?

Oops! Something went wrong while submitting the form.

## FREE course on 'Sorting Algorithms' by Omkar Deshpande (Stanford PhD, Head of Curriculum, IK)

Oops! Something went wrong while submitting the form.

# Equal Subset Partition Problem

In this problem, we will be dividing a given array of integers into two, such that the sums of integers in the subsets are equal. It’s known as the “Equal Subset Partition” problem. You can expect this interview question on arrays at DSA rounds in big tech companies like Amazon.

# Equal Subset Partition Problem Statement

Given an array `s` of `n` integers, partition it into two non-empty subsets, `s1` and `s2`, such that the sum of all elements in `s1` is equal to the sum of all elements in `s2`. Return a boolean array of size `n`, where `i`-th element is 1 if `i`-th element of `s` belongs to `s1` and 0 if it belongs to `s2`.

## Example

``````{
"s": [10, -3, 7, 2, 1, 3]
}
``````

Output:

``````[1, 1, 0, 0, 0, 1]
``````

There are multiple partitionings, where `s1` sums up to 10 and `s2` sums up to 10; they are all correct answers:

`s1 = [ 10 , -3 , 3 ]` and `s2 = [ 7 , 2 , 1 ]` (Sample output)

`s1 = [ 7 , 2 , 1 ]` and `s2 = [ 10 , -3 , 3 ]`

`s1 = [10]` and `s2 = [-3, 3, 7, 2, 1]`

`s1 = [-3, 3, 7, 2, 1]` and `s2 = [10]`

`s1 = [10, -3, 2, 1]` and `s2 = [7, 3]`

`s1 = [7, 3]` and `s2 = [10, -3, 2, 1]`.

## Notes

• Any valid answer will be accepted.
• If such partitioning is not possible, return an empty array.

Constraints:

• 1 <= `n` <= 100
• -100 <= elements in `s` <= 100

We provided two solutions. Throughout the editorial, we will refer to the length of the input array as `n`.

# Equal Subset Partition Solution 1: Brute Force

This partitioning problem can be reduced to finding a subset that sums up to half of the total sum. Also, if the value of the `sum` is odd, then we cannot partition it into two equal subsets. So, in case the value of the `sum` is odd, we simply return an empty array.

In this approach, we iterate over all possible combinations of subsets of the given array and check if the current subset sums to `sum/2`. If we find one such subset, we declare this subset `s1` (the remaining elements then belong to `s2`).

## Time Complexity

O(n * 2n).

We are iterating on all possible subsets, i.e., 2n subsets for an array of size `n`. Hence, we are doing O(2n) iterations and then for each subset, we are computing its sum. To do this we need to iterate over each element of the subset that takes O(n) time of each individual subset. Hence, the total time complexity becomes O(2n) * O(n) ~ O(n * 2n).

## Auxiliary Space Used

O(n).

To generate all partitionings, we recursively backtrack on all indexes of the array. Call stack might take up to O(n) space.

Apart from this, we are only traversing on the given subarray multiple times for different subsets without maintaining any state information. Hence, we do not allocate any space for processing. The only space we allocate is the final return array that is of size `n`. Hence, the total auxiliary space complexity is O(n) + O(n) = O(n).

## Space Complexity

O(n).

Space used by input: O(n).

Auxiliary space used: O(n).

Space used by output: O(n).

So, total space complexity: O(n).

## Code For Equal Subset Partition Solution 1: Brute Force

``````/*
Asymptotic complexity in terms of the length of \`s\` \`n\`:
* Time: O(2^n * n).
* Auxiliary space: O(n).
* Total space: O(n).
*/

// Returns true if the result array \`subsets\` gives
// a valid partition for the input array \`v\`.
bool validator(vector<int> &v, vector<bool> &subsets)
{
// Stores sum of subset s1.
int sum1 = 0;
// Stores sum of subset s2.
int sum2 = 0;
// Counts number of elements in s2.
int sz = count(subsets.begin(), subsets.end(), true);
int n = v.size();

if (sz == 0 or sz == n or subsets.size() != n)
{
return false;
}
// Loop into array v and calculate s1 and s2 sum.
for (int i = 0; i < n; i++)
{
if (subsets[i] == 0)
sum1 += v[i];
else if (subsets[i] == 1)
sum2 += v[i];
else
{ // invalid output
return false;
}
}

if (sum1 != sum2)
{
return false;
}
return true;
}

// Resursive backtracking to generate all subset partition.
void solver(vector<bool> &vis, vector<int> &s, int idx, bool &solution_found)
{
if (idx == s.size())
{
// Check if current partition is valid or not.
solution_found = validator(s, vis);
return;
}

if (!solution_found)
{
solver(vis, s, idx + 1, solution_found);
}

if (!solution_found)
{
// Add current element in subset 1.
vis[idx] = 1;
solver(vis, s, idx + 1, solution_found);
// Remove current element from subset 1.
vis[idx] = solution_found;
}
}

vector<bool> equal_subset_sum_partition(vector<int> &s)
{
// Flag to indicate whether solution is found in recursion.
bool solution_found = false;
vector<bool> result_subset(s.size(), 0);
// Recursively generates all possible partitions
// and checks for solution.
solver(result_subset, s, 0, solution_found);
if (!solution_found)
{
// Empty the array if no result found.
result_subset.clear();
}
return result_subset;
}
``````

# Equal Subset Partition Solution 2: Optimal

As discussed in the brute force approach, we have simply reduced this problem to a subset sum problem, such that given an array `s`, we need to first check if a subset exists with the sum of `sum/2`. If yes, then we need to separate that subset from the rest of the elements of the array. We will be using dynamic programming to solve this problem. Our first aim will be to check if a subset with sum `sum/2` exists or not. To do so, we will be maintaining a 2D DP state as follows:

Boolean `state(idx, sum)`.

Here, `state(idx, sum)` tells us if it is possible to get a subset sum of the sum provided the elements from 0 to `idx` of the given array.

Now, our state transition will look like below:

`state(idx, sum) = state(idx - 1, sum) | state(idx - 1, sum - s[idx])`

So, using the above state transition, we will populate all our DP states. Now, we simply check the value of `state(n - 1, sum / 2)` (assumed 0-based array index). If it is true, then it is possible to partition the given array. If it is false, then we return an empty array.

Now, to get the partitioning, we start a top-down lookup on our DP states. We start from the `state(n - 1, sum / 2)`. If this state is true and `state(n - 2, sum / 2)` is false, this means `s[n - 1]` contributed to the subset sum, and if it is false, we go to `state(n - 2, sum / 2)` to identify our contributors of the subset sum of `sum/2`. We repeat this reverse DP transition until the point we reach the first index of the array or till the point, the required sum becomes 0. While doing these reverse DP transitions, we also mark the contributed elements as `s1` subset elements and the rest of the array as `s2` elements. Because the elements in our array can also be negative, we use a hash-based container like `unordered_map` in C++ to overcome this problem of negative indexing. Refer to the solution for implementation details.

## Time Complexity

O(n * range_sum) since this is a pseudo-polynomial time problem, where `range_sum` is the absolute difference between the maximum sum and the minimum sum possible in the given input array `s`.

As we are visiting all the DP states, i.e., `n * range_sum`, we will be doing `n * range_sum` iterations and for each state, we are doing O(1) amount of work. Also, because of memorization, each state is being visited once. Hence, the total time complexity of this solution is O(n * range_sum).

## Auxiliary Space Used

O(n * range_sum).

Since we are using an auxiliary container of size `n * range_sum` to store the DP states. So, the auxiliary space complexity is O(n * range_sum).

## Space Complexity

O(n * range_sum).

Space used by input: O(n).

Auxiliary space used: O(n * range_sum).

Space used by output: O(n).

So, total space complexity: O(n * range_sum).

## Code For Equal Subset Partition Solution 2: Optimal

``````/*
Asymptotic complexity in terms of the length of \`s\` (\`n\`) and the absolute difference between
the maximum sum and the minimum sum possible in the given input array \`s\` (\`range_sum\`):
* Time: O(n * range_sum).
* Auxiliary space: O(n * range_sum).
* Total space: O(n * range_sum).
*/

vector<bool> equal_subset_sum_partition(vector<int> &s)
{
// Store min and max sum possible for given array.
int sum_neg = 0, sum_pos = 0;
for (auto val : s)
{
if (val < 0)
sum_neg += val;
else
sum_pos += val;
}

// Total sum of the array.
int sum = sum_pos + sum_neg;
// Partition not possible.
if (sum & 1)
{
return vector<bool>();
}

int n = s.size();

// dp state
unordered_map<int, bool> dp[n];

// Base state:
// for idx 0 only one sum s[0] is possible
dp[0][s[0]] = true;

for (int i = 1; i < n; i++)
{
// Iterate on all possible subset sum.
for (int val = sum_neg; val <= sum_pos; val++)
{
// dp state-transition:

// 1) state(i, val) = state(i - 1, val) without taking current element.
dp[i][val] = dp[i - 1][val];

// 2) if val == s[i], just taking i-th element is sufficient.
if (val == s[i])
dp[i][val] = true;
else if (val - s[i] >= sum_neg)
{
// 3) state(i, val) = state(i - 1, val - s[i]) when taking current element.
dp[i][val] |= dp[i - 1][val - s[i]];
}
}
}

int required = sum / 2;
int idx = n - 1;

// Parition not possible.
if (!dp[idx][required])
{
vector<bool> ret;
return ret;
}

// Tracks partition elements.
vector<bool> result_subset(s.size(), 0);
// Tracks count of elements included in S1.
int cnt = 0;
while (idx >= 0)
{
if (idx != 0)
{
// Reverse dp transition.
if (dp[idx][required] and !dp[idx - 1][required])
{
result_subset[idx] = 1;
cnt++;
required -= s[idx];
if (required == 0)
break;
}
}
else
{
result_subset[idx] = 1;
cnt++;
}
idx--;
}

// Checks whether all elements are included in S1.
// All elements will be in S1 if total_sum = 0
// case when s = [-2, 2]
// partition is not possible in this case.
if (cnt == n)
{
result_subset.clear();
}
return result_subset;
}

``````

We hope that these solutions to equal sum subset partition problem have helped you level up your coding skills. You can expect problems like these at top tech companies like Amazon and Google.

If you are preparing for a tech interview at FAANG or any other Tier-1 tech company, register for Interview Kickstart’s FREE webinar to understand the best way to prepare.

Interview Kickstart offers interview preparation courses taught by FAANG+ tech leads and seasoned hiring managers. Our programs include a comprehensive curriculum, unmatched teaching methods, and career coaching to help you nail your next tech interview.

We offer 18 interview preparation courses, each tailored to a specific engineering domain or role, including the most in-demand and highest-paying domains and roles, such as:

### Try yourself in the Editor

Note: Input and Output will already be taken care of.

# Equal Subset Partition Problem

In this problem, we will be dividing a given array of integers into two, such that the sums of integers in the subsets are equal. It’s known as the “Equal Subset Partition” problem. You can expect this interview question on arrays at DSA rounds in big tech companies like Amazon.

# Equal Subset Partition Problem Statement

Given an array `s` of `n` integers, partition it into two non-empty subsets, `s1` and `s2`, such that the sum of all elements in `s1` is equal to the sum of all elements in `s2`. Return a boolean array of size `n`, where `i`-th element is 1 if `i`-th element of `s` belongs to `s1` and 0 if it belongs to `s2`.

## Example

``````{
"s": [10, -3, 7, 2, 1, 3]
}
``````

Output:

``````[1, 1, 0, 0, 0, 1]
``````

There are multiple partitionings, where `s1` sums up to 10 and `s2` sums up to 10; they are all correct answers:

`s1 = [ 10 , -3 , 3 ]` and `s2 = [ 7 , 2 , 1 ]` (Sample output)

`s1 = [ 7 , 2 , 1 ]` and `s2 = [ 10 , -3 , 3 ]`

`s1 = [10]` and `s2 = [-3, 3, 7, 2, 1]`

`s1 = [-3, 3, 7, 2, 1]` and `s2 = [10]`

`s1 = [10, -3, 2, 1]` and `s2 = [7, 3]`

`s1 = [7, 3]` and `s2 = [10, -3, 2, 1]`.

## Notes

• Any valid answer will be accepted.
• If such partitioning is not possible, return an empty array.

Constraints:

• 1 <= `n` <= 100
• -100 <= elements in `s` <= 100

We provided two solutions. Throughout the editorial, we will refer to the length of the input array as `n`.

# Equal Subset Partition Solution 1: Brute Force

This partitioning problem can be reduced to finding a subset that sums up to half of the total sum. Also, if the value of the `sum` is odd, then we cannot partition it into two equal subsets. So, in case the value of the `sum` is odd, we simply return an empty array.

In this approach, we iterate over all possible combinations of subsets of the given array and check if the current subset sums to `sum/2`. If we find one such subset, we declare this subset `s1` (the remaining elements then belong to `s2`).

## Time Complexity

O(n * 2n).

We are iterating on all possible subsets, i.e., 2n subsets for an array of size `n`. Hence, we are doing O(2n) iterations and then for each subset, we are computing its sum. To do this we need to iterate over each element of the subset that takes O(n) time of each individual subset. Hence, the total time complexity becomes O(2n) * O(n) ~ O(n * 2n).

## Auxiliary Space Used

O(n).

To generate all partitionings, we recursively backtrack on all indexes of the array. Call stack might take up to O(n) space.

Apart from this, we are only traversing on the given subarray multiple times for different subsets without maintaining any state information. Hence, we do not allocate any space for processing. The only space we allocate is the final return array that is of size `n`. Hence, the total auxiliary space complexity is O(n) + O(n) = O(n).

## Space Complexity

O(n).

Space used by input: O(n).

Auxiliary space used: O(n).

Space used by output: O(n).

So, total space complexity: O(n).

## Code For Equal Subset Partition Solution 1: Brute Force

``````/*
Asymptotic complexity in terms of the length of \`s\` \`n\`:
* Time: O(2^n * n).
* Auxiliary space: O(n).
* Total space: O(n).
*/

// Returns true if the result array \`subsets\` gives
// a valid partition for the input array \`v\`.
bool validator(vector<int> &v, vector<bool> &subsets)
{
// Stores sum of subset s1.
int sum1 = 0;
// Stores sum of subset s2.
int sum2 = 0;
// Counts number of elements in s2.
int sz = count(subsets.begin(), subsets.end(), true);
int n = v.size();

if (sz == 0 or sz == n or subsets.size() != n)
{
return false;
}
// Loop into array v and calculate s1 and s2 sum.
for (int i = 0; i < n; i++)
{
if (subsets[i] == 0)
sum1 += v[i];
else if (subsets[i] == 1)
sum2 += v[i];
else
{ // invalid output
return false;
}
}

if (sum1 != sum2)
{
return false;
}
return true;
}

// Resursive backtracking to generate all subset partition.
void solver(vector<bool> &vis, vector<int> &s, int idx, bool &solution_found)
{
if (idx == s.size())
{
// Check if current partition is valid or not.
solution_found = validator(s, vis);
return;
}

if (!solution_found)
{
solver(vis, s, idx + 1, solution_found);
}

if (!solution_found)
{
// Add current element in subset 1.
vis[idx] = 1;
solver(vis, s, idx + 1, solution_found);
// Remove current element from subset 1.
vis[idx] = solution_found;
}
}

vector<bool> equal_subset_sum_partition(vector<int> &s)
{
// Flag to indicate whether solution is found in recursion.
bool solution_found = false;
vector<bool> result_subset(s.size(), 0);
// Recursively generates all possible partitions
// and checks for solution.
solver(result_subset, s, 0, solution_found);
if (!solution_found)
{
// Empty the array if no result found.
result_subset.clear();
}
return result_subset;
}
``````

# Equal Subset Partition Solution 2: Optimal

As discussed in the brute force approach, we have simply reduced this problem to a subset sum problem, such that given an array `s`, we need to first check if a subset exists with the sum of `sum/2`. If yes, then we need to separate that subset from the rest of the elements of the array. We will be using dynamic programming to solve this problem. Our first aim will be to check if a subset with sum `sum/2` exists or not. To do so, we will be maintaining a 2D DP state as follows:

Boolean `state(idx, sum)`.

Here, `state(idx, sum)` tells us if it is possible to get a subset sum of the sum provided the elements from 0 to `idx` of the given array.

Now, our state transition will look like below:

`state(idx, sum) = state(idx - 1, sum) | state(idx - 1, sum - s[idx])`

So, using the above state transition, we will populate all our DP states. Now, we simply check the value of `state(n - 1, sum / 2)` (assumed 0-based array index). If it is true, then it is possible to partition the given array. If it is false, then we return an empty array.

Now, to get the partitioning, we start a top-down lookup on our DP states. We start from the `state(n - 1, sum / 2)`. If this state is true and `state(n - 2, sum / 2)` is false, this means `s[n - 1]` contributed to the subset sum, and if it is false, we go to `state(n - 2, sum / 2)` to identify our contributors of the subset sum of `sum/2`. We repeat this reverse DP transition until the point we reach the first index of the array or till the point, the required sum becomes 0. While doing these reverse DP transitions, we also mark the contributed elements as `s1` subset elements and the rest of the array as `s2` elements. Because the elements in our array can also be negative, we use a hash-based container like `unordered_map` in C++ to overcome this problem of negative indexing. Refer to the solution for implementation details.

## Time Complexity

O(n * range_sum) since this is a pseudo-polynomial time problem, where `range_sum` is the absolute difference between the maximum sum and the minimum sum possible in the given input array `s`.

As we are visiting all the DP states, i.e., `n * range_sum`, we will be doing `n * range_sum` iterations and for each state, we are doing O(1) amount of work. Also, because of memorization, each state is being visited once. Hence, the total time complexity of this solution is O(n * range_sum).

## Auxiliary Space Used

O(n * range_sum).

Since we are using an auxiliary container of size `n * range_sum` to store the DP states. So, the auxiliary space complexity is O(n * range_sum).

## Space Complexity

O(n * range_sum).

Space used by input: O(n).

Auxiliary space used: O(n * range_sum).

Space used by output: O(n).

So, total space complexity: O(n * range_sum).

## Code For Equal Subset Partition Solution 2: Optimal

``````/*
Asymptotic complexity in terms of the length of \`s\` (\`n\`) and the absolute difference between
the maximum sum and the minimum sum possible in the given input array \`s\` (\`range_sum\`):
* Time: O(n * range_sum).
* Auxiliary space: O(n * range_sum).
* Total space: O(n * range_sum).
*/

vector<bool> equal_subset_sum_partition(vector<int> &s)
{
// Store min and max sum possible for given array.
int sum_neg = 0, sum_pos = 0;
for (auto val : s)
{
if (val < 0)
sum_neg += val;
else
sum_pos += val;
}

// Total sum of the array.
int sum = sum_pos + sum_neg;
// Partition not possible.
if (sum & 1)
{
return vector<bool>();
}

int n = s.size();

// dp state
unordered_map<int, bool> dp[n];

// Base state:
// for idx 0 only one sum s[0] is possible
dp[0][s[0]] = true;

for (int i = 1; i < n; i++)
{
// Iterate on all possible subset sum.
for (int val = sum_neg; val <= sum_pos; val++)
{
// dp state-transition:

// 1) state(i, val) = state(i - 1, val) without taking current element.
dp[i][val] = dp[i - 1][val];

// 2) if val == s[i], just taking i-th element is sufficient.
if (val == s[i])
dp[i][val] = true;
else if (val - s[i] >= sum_neg)
{
// 3) state(i, val) = state(i - 1, val - s[i]) when taking current element.
dp[i][val] |= dp[i - 1][val - s[i]];
}
}
}

int required = sum / 2;
int idx = n - 1;

// Parition not possible.
if (!dp[idx][required])
{
vector<bool> ret;
return ret;
}

// Tracks partition elements.
vector<bool> result_subset(s.size(), 0);
// Tracks count of elements included in S1.
int cnt = 0;
while (idx >= 0)
{
if (idx != 0)
{
// Reverse dp transition.
if (dp[idx][required] and !dp[idx - 1][required])
{
result_subset[idx] = 1;
cnt++;
required -= s[idx];
if (required == 0)
break;
}
}
else
{
result_subset[idx] = 1;
cnt++;
}
idx--;
}

// Checks whether all elements are included in S1.
// All elements will be in S1 if total_sum = 0
// case when s = [-2, 2]
// partition is not possible in this case.
if (cnt == n)
{
result_subset.clear();
}
return result_subset;
}

``````

We hope that these solutions to equal sum subset partition problem have helped you level up your coding skills. You can expect problems like these at top tech companies like Amazon and Google.

If you are preparing for a tech interview at FAANG or any other Tier-1 tech company, register for Interview Kickstart’s FREE webinar to understand the best way to prepare.

Interview Kickstart offers interview preparation courses taught by FAANG+ tech leads and seasoned hiring managers. Our programs include a comprehensive curriculum, unmatched teaching methods, and career coaching to help you nail your next tech interview.

We offer 18 interview preparation courses, each tailored to a specific engineering domain or role, including the most in-demand and highest-paying domains and roles, such as: