Count Partitions with a Given Difference

73k
0

An array arr contains non-negative integers, and a non-negative integer difference is given. Partition all array elements into two subsets S1 and S2 so every element belongs to exactly one subset.

Count the partitions satisfying sum(S1) >= sum(S2) and sum(S1) - sum(S2) = difference. Equal values at different indices represent different choices. Return the count modulo 1,000,000,007.

Example 1

Input: arr = [5, 2, 6, 4], difference = 3
Output: 1
Explanation: Partition S1 = [6, 4] and S2 = [5, 2] gives sums 10 and 7, so the required difference equals 3.

Example 2

Input: arr = [0, 0, 1], difference = 1
Output: 4
Explanation: Value 1 must belong to S1, while each indexed zero may belong to either subset. Four index-based assignments preserve subset sums 1 and 0.

Recursion

The two subset sums together equal the total array sum, while their difference is fixed. Combining these two conditions determines the required sum of the smaller subset. Therefore, instead of explicitly finding both subsets, we only need to count subsets with this target sum; the remaining elements automatically form the other subset.

Each array index offers two choices for S2: skip the current value or take it if it does not exceed the remaining target. The state solve(index, target) counts valid selections using indices 0 through index. The initial call is solve(N - 1, target) because the complete array must be available for the first decision.

Algorithm

  • Calculate totalSum by adding all array values because the two subset sums must together equal the complete array sum.

  • Reject the case where totalSum - difference is negative or odd because it cannot produce a valid non-negative integer target for S2.

  • Set target = (totalSum - difference) / 2 because every subset with this sum represents one valid partition.

  • Start with solve(N - 1, target) because every array element must be considered for the target subset.

  • Handle index == 0 carefully, returning 2 when both target == 0 and arr[0] == 0 because taking or skipping zero creates two distinct selections.

  • Explore the skip choice with the same target because the current value may not belong to S2.

  • Explore the take choice when arr[index] <= target because the current value can then be included without making the remaining target negative.

  • Add both branch counts modulo 1,000,000,007 because the two choices represent disjoint subset selections and the count must remain within the required modular range.

Dry Run

Count Partitions with Given Difference Recursion

Count Partitions with Given Difference Recursion

Solution

#include <bits/stdc++.h>
using namespace std;
class Solution {
private:
int mod = 1000000007;
// Counts target-sum subsets through one index.
int solve(int index, int target, vector<int>& arr) {
// A zero creates two distinct zero-sum choices.
if (index == 0 && target == 0 && arr[0] == 0) {
return 2;
}
// An empty choice or one matching value works.
if (index == 0 && (target == 0 || target == arr[0])) {
return 1;
}
// No valid selection reaches another first-index state.
if (index == 0) {
return 0;
}
// Skipping preserves the required remaining sum.
int notTake = solve(index - 1, target, arr);
int take = 0;
// Taking is legal only within the remaining target.
if (arr[index] <= target) {
// Taking removes the current value from the target.
take = solve(index - 1, target - arr[index], arr);
}
// Both disjoint choices contribute valid selections.
return (notTake + take) % mod;
}
public:
// Counts partitions with the requested sum difference.
int countPartitions(vector<int>& arr, int difference) {
int n = arr.size();
int totalSum = 0;
// The complete sum connects both subset equations.
for (int value : arr) {
totalSum += value;
}
int remaining = totalSum - difference;
// A negative or odd remainder cannot form S2.
if (remaining < 0 || remaining % 2 != 0) {
return 0;
}
// The smaller subset sum becomes the counting target.
int target = remaining / 2;
// Every index remains available at the starting state.
return solve(n - 1, target, arr);
}
};
// Driver code
int main() {
vector<int> arr = {0, 0, 1};
int difference = 1;
Solution obj;
cout << obj.countPartitions(arr, difference);
return 0;
}

Complexity Analysis

Time Complexity: O(2N), where N is the number of array elements, because each index can create a take branch and a skip branch, forming a binary recursion tree.

Space Complexity: O(N), because the deepest recursive path can contain one call for each array index.

Note: Direct recursion may fail for large input values. Repeated subproblems create exponential work, so an online judge may report Time Limit Exceeded.

Memoization

Direct recursion reaches the same pair of index and target through different earlier choices. Every repeated state produces the same count, so recalculating the complete recursive subtree adds no new information.

A two-dimensional array named dp stores each finished state. A stored value returns immediately during the next visit, while the recursive take-or-skip meaning stays unchanged.

Algorithm

  • Begin with the same transformed target, because memoization improves repeated subset counting without changing the partition reduction.

  • Create dp with n rows and target + 1 columns filled with -1, so every untouched cell marks an uncalculated state.

  • Preserve the special first-index cases, because a zero with target 0 still represents both a take choice and a skip choice.

  • Return dp[index][target] whenever a stored count exists, because every later visit represents the same remaining decisions.

  • Compute the skip branch with an unchanged target, then compute a fitting take branch so both possible memberships reach the cache.

  • Store the two-branch sum modulo 1,000,000,007, so future visits avoid the complete repeated subtree.

  • Return the stored count for (n - 1, target), because the starting state covers every indexed element.

Dry Run

count-partitions-memoization-dp-minus-one.png

count-partitions-memoization-dp-minus-one.png

Solution

#include <bits/stdc++.h>
using namespace std;
class Solution {
private:
int mod = 1000000007;
// Counts target-sum subsets through one index.
int solve(
int index,
int target,
vector<int>& arr,
vector<vector<int>>& dp
) {
// A zero creates two distinct zero-sum choices.
if (index == 0 && target == 0 && arr[0] == 0) {
return 2;
}
// An empty choice or one matching value works.
if (index == 0 && (target == 0 || target == arr[0])) {
return 1;
}
// No valid selection reaches another first-index state.
if (index == 0) {
return 0;
}
// A cached count avoids the repeated recursive tree.
if (dp[index][target] != -1) {
return dp[index][target];
}
// Skipping preserves the required remaining sum.
int notTake = solve(index - 1, target, arr, dp);
int take = 0;
// Taking is legal only within the remaining target.
if (arr[index] <= target) {
// Taking removes the current value from the target.
take = solve(
index - 1, target - arr[index], arr, dp
);
}
// The cache stores the merged disjoint choices.
dp[index][target] = (notTake + take) % mod;
return dp[index][target];
}
public:
// Counts partitions with the requested sum difference.
int countPartitions(vector<int>& arr, int difference) {
int n = arr.size();
int totalSum = 0;
// The complete sum connects both subset equations.
for (int value : arr) {
totalSum += value;
}
int remaining = totalSum - difference;
// A negative or odd remainder cannot form S2.
if (remaining < 0 || remaining % 2 != 0) {
return 0;
}
// The smaller subset sum becomes the counting target.
int target = remaining / 2;
// Negative cells mark uncalculated recursive states.
vector<vector<int>> dp(
n, vector<int>(target + 1, -1)
);
// Every index remains available at the starting state.
return solve(n - 1, target, arr, dp);
}
};
// Driver code
int main() {
vector<int> arr = {0, 0, 1};
int difference = 1;
Solution obj;
cout << obj.countPartitions(arr, difference);
return 0;
}

Complexity Analysis

Time Complexity: O(N × target), where N is the number of array elements and target is the target sum, because at most N × (target + 1) states are calculated once with constant work per state.

Space Complexity: O(N × target + N), because the dp table stores all index-and-sum states, while the recursion stack can reach a depth of N.

Tabulation

Memoization still spends stack space on recursive calls. Tabulation writes the same state answers row by row, so every earlier state is ready before a later index needs the value.

Cell dp[index][currentTarget] stores the number of subsets reaching currentTarget with indices 0 through index. The first row preserves the special zero behavior, and every later row combines the same skip and take choices used by recursion.

Algorithm

  • Begin with the same feasibility checks and transformed target, because tabulation solves the unchanged subset-counting problem.

  • Create dp with n rows and target + 1 columns filled with zero, so every cell can collect valid selection counts.

  • Set dp[0][0] to 2 for a first value of zero and 1 otherwise, because zero supports both take and skip choices without changing the sum.

  • Set dp[0][arr[0]] to 1 for a non-zero first value inside the target, because taking the first value forms one indexed subset.

  • Fill rows from index 1 onward, because every transition reads only the completely prepared preceding row.

  • Add the preceding-row skip count and any legal take count modulo 1,000,000,007, preserving both disjoint decisions for each state.

  • Return dp[n - 1][target], because the last row represents every array index and the required smaller-subset sum.

Dry Run

Count Partitions with Given Difference Tabulation

Count Partitions with Given Difference Tabulation

Solution

#include <bits/stdc++.h>
using namespace std;
class Solution {
private:
int mod = 1000000007;
public:
// Counts partitions with the requested sum difference.
int countPartitions(vector<int>& arr, int difference) {
int n = arr.size();
int totalSum = 0;
// The complete sum connects both subset equations.
for (int value : arr) {
totalSum += value;
}
int remaining = totalSum - difference;
// A negative or odd remainder cannot form S2.
if (remaining < 0 || remaining % 2 != 0) {
return 0;
}
// The smaller subset sum becomes the counting target.
int target = remaining / 2;
// Each cell counts subsets for one index and sum.
vector<vector<int>> dp(
n, vector<int>(target + 1, 0)
);
// A leading zero has take and skip zero-sum choices.
if (arr[0] == 0) {
dp[0][0] = 2;
} else {
dp[0][0] = 1;
}
// A non-zero first value creates one matching subset.
if (arr[0] != 0 && arr[0] <= target) {
dp[0][arr[0]] = 1;
}
// Every row uses only the completed preceding row.
for (int index = 1; index < n; index++) {
for (
int currentTarget = 0;
currentTarget <= target;
currentTarget++
) {
// Skipping keeps the same target count.
int notTake = dp[index - 1][currentTarget];
int take = 0;
// Taking is legal only within the current target.
if (arr[index] <= currentTarget) {
// The earlier row supplies the reduced target.
take = dp[index - 1][
currentTarget - arr[index]
];
}
// Both disjoint choices build the current state.
dp[index][currentTarget] =
(notTake + take) % mod;
}
}
// The last row includes every array index.
return dp[n - 1][target];
}
};
// Driver code
int main() {
vector<int> arr = {0, 0, 1};
int difference = 1;
Solution obj;
cout << obj.countPartitions(arr, difference);
return 0;
}

Complexity Analysis

Time Complexity: O(N × target), where N is the number of array elements and target is the target sum, because every index-and-sum state performs one skip transition and at most one take transition, both in constant time.

Space Complexity: O(N × target), because the two-dimensional dp table stores a count for every index and sum from 0 through target, while iterative tabulation uses no recursion stack.

Space Optimization

Tabulation reads only the preceding row while building a new row. Older rows never contribute to a later transition, so a full two-dimensional table stores more history than the recurrence needs.

Array previous holds counts for the preceding index, and array current receives counts for the active index. Every current count still adds the matching skip and take counts. Assigning current to previous after a completed row preserves the exact row order.

Algorithm

  • Begin with the same transformed target, because space optimization changes storage alone and preserves every DP state meaning.

  • Create previous with target + 1 cells, so one row can represent all sums for the first array index.

  • Initialize previous[0] as 2 for a leading zero and 1 otherwise, because the first row must preserve every valid zero-sum choice.

  • Create a fresh zero-filled current row for each later index, because active updates must read only unchanged counts from previous.

  • Calculate every current[currentTarget] from the skip count and any legal take count, preserving the tabulation transition exactly.

  • Shift current into previous only after the full row is complete, because an early shift would mix states from different indices.

  • Return previous[target] after the final shift, because the retained row then represents all array indices.

Dry Run

Count Partitions with Given Difference Space Optimization

Count Partitions with Given Difference Space Optimization

Solution

#include <bits/stdc++.h>
using namespace std;
class Solution {
private:
int mod = 1000000007;
public:
// Counts partitions with the requested sum difference.
int countPartitions(vector<int>& arr, int difference) {
int n = arr.size();
int totalSum = 0;
// The complete sum connects both subset equations.
for (int value : arr) {
totalSum += value;
}
int remaining = totalSum - difference;
// A negative or odd remainder cannot form S2.
if (remaining < 0 || remaining % 2 != 0) {
return 0;
}
// The smaller subset sum becomes the counting target.
int target = remaining / 2;
// One row stores counts for the preceding index.
vector<int> previous(target + 1, 0);
// A leading zero has take and skip zero-sum choices.
if (arr[0] == 0) {
previous[0] = 2;
} else {
previous[0] = 1;
}
// A non-zero first value creates one matching subset.
if (arr[0] != 0 && arr[0] <= target) {
previous[arr[0]] = 1;
}
// A fresh row protects preceding-index values.
for (int index = 1; index < n; index++) {
vector<int> current(target + 1, 0);
for (
int currentTarget = 0;
currentTarget <= target;
currentTarget++
) {
// Skipping keeps the same preceding-row count.
int notTake = previous[currentTarget];
int take = 0;
// Taking is legal only within the current target.
if (arr[index] <= currentTarget) {
// The preceding row supplies the reduced target.
take = previous[
currentTarget - arr[index]
];
}
// Current combines both choices for one state.
current[currentTarget] =
(notTake + take) % mod;
}
// Shift current only after the row is complete.
previous = current;
}
// The retained row includes every array index.
return previous[target];
}
};
// Driver code
int main() {
vector<int> arr = {0, 0, 1};
int difference = 1;
Solution obj;
cout << obj.countPartitions(arr, difference);
return 0;
}

Complexity Analysis

Time Complexity: O(N × target), where N is the number of array elements and target is the target sum, because every index calculates the result for each possible sum from 0 through target.

Space Complexity: O(target), because only the previous and current rows are retained, while all older rows are discarded.

Interview follow-up Questions

Equations S1 + S2 = totalSum and S1 - S2 = difference give 2 * S2 = totalSum - difference. Counting subsets with the resulting S2 sum counts valid partitions.

Dynamic Programming

Read Similar Blogs

Dynamic Programming

Largest Divisible Subset

Given an array nums containing distinct positive integers, return a maximum-length subset. For every pair of values first and second in the subset, either first % second == 0 or secon...

73.5k
Dynamic Programming

Best Time to Buy and Sell Stock IV: At Most K Transactions

Given an integer k and an array prices , prices[day] stores the stock price on a particular day. At most k transactions may be completed. One transaction contains one buy followed by...

50.8k
Dynamic Programming

Best Time to Buy and Sell Stock with Transaction Fee

An array prices stores a stock price for each day, and an integer fee gives the cost of one completed transaction. Any number of transactions may be completed, but only one share may be held at a t...

65.7k
Comments0