#Pyth, 64 bytes

Pyth, 64 bytes

Uses http://stackoverflow.com/a/2163753/4230423 except that a)No cache since Pyth automatically memoizes, b)Prints each instead of appending to list, and c) is translated to Pyth.

Uses https://stackoverflow.com/a/2163753/4230423 except that a)No cache since Pyth automatically memoizes, b)Prints each instead of appending to list, and c) is translated to Pyth.

#Pyth, 68 bytes

try it here online.

M?smg-Gddr1h?H<HGGG1Akd,QOgQQWQFNr1h?k<kQQKg-QNNI<dKB=d-dK)N=kN=Q-QN

M                Lambda g(G,H)
 ?         G     If G truthy
  s              Sum
   m             Map
    g            Recursive call
     -Gdd        G-d,d
    r            Range
     1           1 to
     h           +1
      ? <HG      If H<G (this does min)
       H         H
       G         Else G
   1             Else 1
A                Double assign
 kd              Vars k and d
 ,               To vals
  Q              Q (evaled input)
  O              Randrange 0 till val
   gQQ           Call g(Q, Q)
WQ               While Q is truthy
 FN              For N in
  r              Range
   1             From one
   h             Till +1
    ?k<kQQ       Min(Q,K)
  Kg             K=g(
   -QN           Q-N
   N             N
  I<dK           If d<k
   B             Break (implicit close paren)
  =d-dk          Subtracts d-=k
 )               Close out for loop
 N               Prints N
 =kN             Set k=N
 =Q-QN           Subtracts Q-=N

#Pyth, 64 bytes

M?smg-Gddr1hhS,GHG1Akd,QOgQQWQFNr1hhS,QkKg-QNNI<dKB-=dK)N=kN-=QN

M                Lambda g(G,H)
 ?         G     If G truthy
  s              Sum
   m             Map
    g            Recursive call
     -Gdd        G-d,d
    r            Range
     1           1 to
     h           +1
      hS         First element of sorted (does min)
       ,GH       From G and H
   1             Else 1
A                Double assign
 kd              Vars k and d
 ,               To vals
  Q              Q (evaled input)
  O              Randrange 0 till val
   gQQ           Call g(Q, Q)
WQ               While Q is truthy
 FN              For N in
  r              Range
   1             From one
   h             Till +1
    hS,QK        Min(Q,K)
  Kg             K=g(
   -QN           Q-N
   N             N
  I<dK           If d<k
   B             Break (implicit close paren)
  -=dk           Subtracts d-=k
 )               Close out for loop
 N               Prints N
 =kN             Set k=N
 -=QN            Subtracts Q-=N