Pattern Guide
Balanced Partition DP
"Split array into groups with balanced sums. Fairness DP, multiway partition."
Balanced partition problems ask to divide elements into groups to minimize/maximize some balance metric: equal sum halves, k groups with min max-sum, fair distribution. Techniques: bitmask DP (small n), subset-sum bitset (split into two equal halves), binary search + greedy (minimize maximum), and DP over sorted arrays with running bounds.
Problems you can solve with this pattern
3 problems · click any to start solving
// 1. Two-way split: minimize |S1 - S2|
function minDiffPartition(nums) {
const total = nums.reduce((a,b)=>a+b,0);
// Bitset DP: which sums ≤ total/2 are achievable?
let dp = 1n; // BigInt bitset
for (const n of nums) dp |= dp << BigInt(n);
const half = total >> 1;
for (let s = half; s >= 0; s--)
if ((dp >> BigInt(s)) & 1n) return total - 2 * s;
return total; // shouldn't reach
}
// 2. k-way split: minimize maximum group sum (binary search + greedy)
function minMaxPartition(nums, k) {
let lo = Math.max(...nums), hi = nums.reduce((a,b)=>a+b,0);
const check = (limit) => {
let groups = 1, cur = 0;
for (const n of nums) {
if (cur + n > limit) { groups++; cur = 0; }
cur += n;
}
return groups <= k;
};
while (lo < hi) {
const mid = (lo + hi) >> 1;
check(mid) ? hi = mid : lo = mid + 1;
}
return lo;
}
// 3. k groups of equal sum (bitmask DP for small n)
function canPartitionKSubsets(nums, k) {
const total = nums.reduce((a,b)=>a+b,0);
if (total % k !== 0) return false;
const target = total / k;
const n = nums.length;
const dp = new Array(1 << n).fill(false); dp[0] = true;
const sums = new Array(1 << n).fill(0);
for (let mask = 0; mask < (1 << n); mask++) {
if (!dp[mask]) continue;
for (let i = 0; i < n; i++) {
if ((mask >> i) & 1) continue;
const next = mask | (1 << i);
const newSum = (sums[mask] + nums[i]) % target;
if (sums[mask] + nums[i] <= target) {
sums[next] = newSum;
dp[next] = true;
}
}
}
return dp[(1 << n) - 1];
}Balanced partition problems come in several flavors: (1) two-way split minimizing difference → subset sum DP to target sum/2; (2) k-way split minimizing maximum group sum → binary search + greedy; (3) equal-sum k groups → bitmask DP tracking which elements are used; (4) split into groups with size constraints → DP with group size tracking. The key: identify what "balanced" means and choose the matching technique.
// 1. Two-way split: minimize |S1 - S2|
function minDiffPartition(nums) {
const total = nums.reduce((a,b)=>a+b,0);
// Bitset DP: which sums ≤ total/2 are achievable?
let dp = 1n; // BigInt bitset
for (const n of nums) dp |= dp << BigInt(n);
const half = total >> 1;
for (let s = half; s >= 0; s--)
if ((dp >> BigInt(s)) & 1n) return total - 2 * s;
return total; // shouldn't reach
}
// 2. k-way split: minimize maximum group sum (binary search + greedy)
function minMaxPartition(nums, k) {
let lo = Math.max(...nums), hi = nums.reduce((a,b)=>a+b,0);
const check = (limit) => {
let groups = 1, cur = 0;
for (const n of nums) {
if (cur + n > limit) { groups++; cur = 0; }
cur += n;
}
return groups <= k;
};
while (lo < hi) {
const mid = (lo + hi) >> 1;
check(mid) ? hi = mid : lo = mid + 1;
}
return lo;
}
// 3. k groups of equal sum (bitmask DP for small n)
function canPartitionKSubsets(nums, k) {
const total = nums.reduce((a,b)=>a+b,0);
if (total % k !== 0) return false;
const target = total / k;
const n = nums.length;
const dp = new Array(1 << n).fill(false); dp[0] = true;
const sums = new Array(1 << n).fill(0);
for (let mask = 0; mask < (1 << n); mask++) {
if (!dp[mask]) continue;
for (let i = 0; i < n; i++) {
if ((mask >> i) & 1) continue;
const next = mask | (1 << i);
const newSum = (sums[mask] + nums[i]) % target;
if (sums[mask] + nums[i] <= target) {
sums[next] = newSum;
dp[next] = true;
}
}
}
return dp[(1 << n) - 1];
}- 2 groups, min diff: subset-sum DP to target=sum/2, O(n × sum)
- k groups, min max: binary search + greedy, O(n log sum)
- k groups, equal sum, small n (≤20): bitmask DP, O(2^n × n)
- k groups, equal size: sort + pair, or DP by sorted order
Bitmask DP tip: For "can we partition into k equal-sum groups," track partial current bucket sum mod target. An element adds to the current bucket or starts a new one when bucket fills.