Standard Bar Recursion · Subsequences Pattern O(2^N) branch walks plus O(2^N log 2^N) for the sort · O(N) recursion depth beyond the output
A freight planner wants to see the weight of every possible load that could leave the ramp, where a load is any subset of the parked pallets — including the empty truck. Walking the pallet line once and branching take-or-skip at each pallet produces the full ledger of load weights, which the planner then reads in ascending order.
Input: An array arr of N non-negative integers.
Output: The sum of every subset, sorted in ascending order.
1 <= N <= 150 <= arr[i] <= 10^4Input: {"arr":[2,3]}
Output: [0,2,3,5]
Take nothing (0), either pallet alone (2, 3), or both (5), then read in order.
Input: {"arr":[5,2,1]}
Output: [0,1,2,3,5,6,7,8]
Eight subsets, and their sums happen to run cleanly from 0 to 8.