mediumRecursionPattern: Mixed
Container Distribution Count Solution
Problem Statement
Given an array of container capacities `capacities` and an array of ship capacities `ships`, find the total number of ways to distribute the containers among the ships such that the sum of container capacities does not exceed the ship's capacity and the number of containers does not exceed the ship's capacity. If no such distribution is possible, return -1.
Examples
Example 1:
Input:{"capacities":[1,2,3],"ships":[4,5]}
Output:3
Explanation: The possible distributions are: [1, 2] in the first ship and [3] in the second ship, [1, 3] in the first ship and [2] in the second ship, [2, 3] in the first ship and [1] in the second ship
Constraints
- 1 <= shipCapacity <= 100
- 1 <= containerCapacities.length <= 20
- 1 <= containerCapacities[i] <= 50
Time: O(2^n) Space: O(n)
The optimized approach uses recursion and backtracking to explore all possible distributions of containers among the ships, resulting in a time complexity of O(2^n). This approach is more efficient than the brute-force approach but still may not be practical for very large inputs.
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.