#!/usr/bin/perl
# decompose sums to sets of summands

use strict;
use warnings;

my $sum=80;
my @sets;
my @latest=($sum);
my $higherthan3=0; #the position of the last number higher than 3
my $sumof3sand2s=0; #all the 3s and 2s summed up;

while (1) {

# @latest is always sorted from highest to lowest number
    
#calculate the next set 

    #1: special case 3 3 and a string of 2s
    my $i= $#latest;
    $i-- while ($i>0 and $latest[$i]==2);
    if ($i>0 and $latest[$i]==3 and $latest[$i-1]==3) {
	$latest[$i-1]=2;
	$latest[$i]=2;
	push @latest, 2;
    }
    else {

	#2: get the last number higher than 3. If there is none, stop
	$i= $higherthan3; 
	last if ($i==-1);
	
	#3: if that number is also the last number at all, produce a 2 after it 
	if ($i==$#latest) {
	    $latest[$i]-= 2;
	    push (@latest, 2);
	    $sumof3sand2s+=2;
	    if ($latest[$i]<=3) {
		$higherthan3--;
		$sumof3sand2s+=$latest[$i];
	    }
	}
	#4: otherwise cut off at this point, decrease it and put the rest 
	#   to the right of it with the highest possible numbers
	else {
	    $#latest=$i;
	    $latest[$i]--;
	    my $x= $latest[$i];
	    my $leftover= $sumof3sand2s+1;
	    $sumof3sand2s=0;
	    my $foundpoint=0; #is true after the higherthan3 point was found
	    if ($x<=3) {
		$sumof3sand2s=$x+$leftover;
		$foundpoint++;
		$higherthan3= $i-1;
	    }
	    while($leftover>$x) {
		$i++;
		if ($leftover>$x+1) {
		    push(@latest,$x);
		    $leftover-= $x;
		}
		else {
		    push @latest, $x-1;
		    $leftover-= ($x-1);
		    if ($x==4) {
			$sumof3sand2s=3+$leftover;
			$foundpoint++;
			$higherthan3= $i-1;
		    }
		}
	    }
	    if ($leftover>1) {
		push(@latest, $leftover);
		if ($leftover>3) {
		    $higherthan3=$#latest;
		}
		elsif (not $foundpoint) { 
		    $higherthan3= $#latest-1;
		    $sumof3sand2s+= $leftover;
		}
	    }
	    die "Internal Error" if ($leftover==1);
	} 
    }
    #push @sets, join(',',@latest);
    #print join(',',@latest),"\n";
} 
print join("\n",@sets),"\n";

print @sets+0,"\n";
#------------------