Equal Payload Partition — Problem Statement & Solution Guide
Problem Description
Given an array of integers weights representing package weights, determine the number of ways to distribute these packages evenly into two groups, such that the total weight of packages in both groups is equal. The order of packages within each group does not matter, and each package can only be assigned to one group.
Examples
Input
[1, 3]
Output
2
Explanation: Step-by-step: Given the input [1, 3], we can distribute the packages into two groups as (1, 3) or (3, 1). Since the order of packages within each group does not matter, these two distributions are considered the same. Therefore, the output is 2.
Input
[2, 3]
Output
1
Explanation: Step-by-step: Given the input [2, 3], we can distribute the packages into two groups as (2, 3) or (3, 2). Since the order of packages within each group does not matter, these two distributions are considered the same. Therefore, the output is 1.
Constraints
- {"name":"Package Weights","type":"integer array","minLength":1,"maxLength":20,"minValue":1,"maxValue":100}
Optimal Approach & Strategy
The optimized approach uses recursion with memoization to efficiently explore all possible subsets of the given package weights. It uses a helper function to recursively assign packages to the two spacecraft and checks if the sums of the packages in both spacecraft are equal.
Brute Force Approach
The brute-force approach involves generating all possible subsets of the given package weights and checking if the sum of each subset is equal to half of the total weight. This approach has an exponential time complexity due to the generation of all subsets. It can be implemented using nested loops to generate all possible combinations of packages.
Verified Code Solutions
function equalPartition(weights) {
const n = weights.length;
let totalSum = 0;
for (let i = 0; i < n; i++) {
totalSum += weights[i];
}
if (totalSum % 2 !== 0) {
return 0;
}
if (n === 0) {
return 0;
}
const targetSum = totalSum / 2;
const dp = new Array(n + 1).fill(0).map(() => new Array(targetSum + 1).fill(0));
dp[0][0] = 1;
for (let i = 1; i <= n; i++) {
for (let j = 1; j <= targetSum; j++) {
if (weights[i - 1] > j) {
dp[i][j] = dp[i - 1][j];
} else {
dp[i][j] = dp[i - 1][j] + dp[i - 1][j - weights[i - 1]];
}
}
}
return dp[n][targetSum] / 2;
}public int equalPayloadPartition(int[] weights) {
int totalSum = 0;
for (int weight : weights) {
totalSum += weight;
}
if (totalSum % 2 != 0) {
return 0;
}
int targetSum = totalSum / 2;
int[] dp = new int[targetSum + 1];
dp[0] = 1;
for (int weight : weights) {
for (int i = targetSum; i >= weight; i--) {
dp[i] += dp[i - weight];
}
}
return dp[targetSum];
}def equal_payload_partition(weights):
total_sum = sum(weights)
if total_sum % 2 != 0:
return 0
target_sum = total_sum // 2
dp = [0] * (target_sum + 1)
dp[0] = 1
for weight in weights:
for i in range(target_sum, weight - 1, -1):
dp[i] += dp[i - weight]
return dp[target_sum]function equalPartition(weights) {
const n = weights.length;
let totalSum = 0;
for (let i = 0; i < n; i++) {
totalSum += weights[i];
}
if (totalSum % 2 !== 0) {
return 0;
}
if (n === 0) {
return 0;
}
const targetSum = totalSum / 2;
const dp = new Array(n + 1).fill(0).map(() => new Array(targetSum + 1).fill(0));
dp[0][0] = 1;
for (let i = 1; i <= n; i++) {
for (let j = 1; j <= targetSum; j++) {
if (weights[i - 1] > j) {
dp[i][j] = dp[i - 1][j];
} else {
dp[i][j] = dp[i - 1][j] + dp[i - 1][j - weights[i - 1]];
}
}
}
return dp[n][targetSum] / 2;
}Asked in Top Tech Interviews
Solve in Interative Editor
Ready to test your code? Open our built-in compiler, run custom test suites, and see detailed complexity analysis reports instantly.