mediumRecursionPattern: Mixed
Equal Payload Partition Solution
Problem Statement
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
Example 1:
Input:[1, 1, 2]
Output:2
Explanation: Two possible distributions: [1, 1] in Starblade and [2] in NovaSpur, or [1, 2] in Starblade and [1] in NovaSpur
Example 2:
Input:[1, 2, 3, 4]
Output:0
Explanation: No possible distribution where both spacecraft have the same total weight
Constraints
- {"name":"Package Weights","type":"integer array","minLength":1,"maxLength":20,"minValue":1,"maxValue":100}
Time: O(2^n) Space: O(n)
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.
Run, Test & Submit Code
Ready to practice this challenge? Launch our interactive compilation environment with compiler validation.
Solve on Interactive WorkspaceTested Solutions
No solution code is currently loaded.
Complete this code in the workspace editor.