You have a bunch of heavy boxes and you want to stack them in the fewest number of stacks possible. The issue is that you can't stack more boxes on a box than it can support, so heavier boxes must go on the bottom of a stack.

The Challenge

Input: A list of weights of boxes, in whole kg.

Output: A list of lists describing the stacks of boxes. This must use the fewest number of stacks possible for the input. To be a valid stack, the weight of each box in the stack must be greater than or equal to the sum of the weight of all boxes above it.

Examples of Valid stacks

(In bottom to top order)

• [3]


• [1, 1]


• [3, 2, 1]


• [4, 2, 1, 1]


• [27, 17, 6, 3, 1]


• [33, 32, 1]


• [999, 888, 99, 11, 1]

Examples of Invalid stacks

(In order from bottom to top)

• [1, 2]


• [3, 3, 3]


• [5, 5, 1]


• [999, 888, 777]


• [4, 3, 2]


• [4321, 3000, 1234, 321]

Example Test Cases

1

IN: [1, 2, 3, 4, 5, 6, 9, 12]
OUT: [[12, 6, 3, 2, 1], [9, 5, 4]]

2

IN: [87, 432, 9999, 1234, 3030]
OUT: [[9999, 3030, 1234, 432, 87]]

3

IN: [1, 5, 3, 1, 4, 2, 1, 6, 1, 7, 2, 3]
OUT: [[6, 3, 2, 1], [7, 4, 2, 1], [5, 3, 1, 1]]

Rules and Assumptions

• Standard I/O rules and banned loopholes apply


• Use any convenient format for I/O
  
  
  • Stacks may be described top to bottom or bottom to top, as long as you are consistent.
  
  
  • The order of stacks (rather than boxes within those stacks) does not matter.
  
  


• If there is more than one optimal configuration of stacks, you may output any one of them


• You may assume that there is at least one box and that all boxes weigh at least 1 kg


• You must support weights up to 9,999 kg, at minimum.


• You must support up to 9,999 total boxes, at minimum.


• Boxes with the same weight are indistinguishable, so there is no need to annotate which box was used where.

Happy golfing! Good luck!

JavaScript (Node.js), 139 bytes

Much faster.

f=(A,s=[])=>(g=([n,...a],s)=>n?s.some((b,i,[...c])=>n<eval(b.join`+`)?0:g(a,c,c[i]=[n,...b]))&&A:A=s)(A.sort((a,b)=>a-b),s)||f(A,[[],...s])

Try it online!

JavaScript (ES6),  157  143 bytes

A=>(g=([n,...a],s=[])=>n?s.map((b,i,[...c])=>n<eval(b.join`+`)||g(a,c,c[i]=[n,...b]),g(a,[...s,[n]]))&&A:A[s.length]?A=s:A)(A.sort((a,b)=>a-b))

Try it online!

Commented

A => ( // A[] = input array, re-used to store the best stacks
 g = ( // g is a recursive function taking:
 [n, // n = next weight to process
 ...a], // a[] = array of remaining weights
 s = [] // s[] = list of stacks
 ) => //
 n ? // if n is defined:
 s.map((b, i, // for each stack b[] at position i in s[],
 [...c]) => // using c[] as a copy of s[]:
 n < eval(b.join`+`) || // if n is heavy enough to support all values in b[]:
 g(a, c, c[i] = [n, ...b]), // do a recursive call with n prepended to c[i]
 g(a, [...s, [n]]) // do a recursive call with a new stack containing n
 ) && A // end of map(); yield A
 : // else:
 A[s.length] ? A = s : A // if s[] is shorter than A[], update A[] to s[]
)(A.sort((a, b) => a - b)) // initial call to g with A[] sorted in ascending order

Jelly, 22 bytes

Œ!ŒṖ€ẎṢ€€ṖÄ>ḊƲ€¬ȦƊƇLÞḢ

Try it online!

Top to bottom.

Python 3, 112 bytes

R=range
f=lambda b:[[b[j::i]for j in R(i)]for i in R(1,len(b))if all(b[j]*2>=sum(b[j::i])for j in R(len(b)))][0]

Try it online!

Takes input in sorted decreasing order. If that isn't allowed, it can be done for 148 bytes: (-10 bytes thanks to @Joel)

R=range
V=lambda a:sorted(a)[::-1]
f=lambda b:[[V(b)[j::i]for j in R(i)]for i in R(1,len(b))if all(V(b)[j]*2>=sum(V(b)[j::i])for j in R(len(b)))][0]

or in Python 3.8 for 131:

R=range
f=lambda b:[[(b:=sorted(b)[::-1])[j::i]for j in R(i)]for i in R(1,len(b))if all(b[j]*2>=sum(b[j::i])for j in R(len(b)))][0]