#include <stdio.h>

long gcd(long a, long b)
{
    while (b != 0)
    {
        long c = a % b;
        a = b;
        b = c;
    }
    return a;
}

long lcm(long a, long b)
{
    return a * (b / gcd(a, b));
}

inline long sumUpTo(long n) { return n*(n+1)/2; }


#define MAX_NR_SET 20000
bool selected[MAX_NR_SET+1];
bool found_set;

int assigned_to[MAX_NR_SET+1];
int buckets[20];

bool knapsack(int nr_buckets, int nr_buckets_in_use, int left, bool printsol, long maxmul)
{
    while (left > 0 && !selected[left])
        left--;
    if (left == 0)
    {
        if (nr_buckets == nr_buckets_in_use)
        {
            if (printsol)
            {
                //printf("%d buckets: ", nr_buckets);
                for (int b = 0; b < nr_buckets; b++)
                {
                    char *sep = " ";
                    for (int i = 1; i <= maxmul; i++)
                        if (selected[i] && assigned_to[i] == b)
                        {
                            printf("%s%d", sep, i);
                            sep = "+";
                        }
                }
                //printf("\n");        
            }
            return true;
        }
        return false;
    }
    bool found = false;
    for (int i = 0; !found && i < nr_buckets && i <= nr_buckets_in_use; i++)
        if (buckets[i] - left >= 0)
        {
            assigned_to[left] = i;
            buckets[i] -= left;
            found = knapsack(nr_buckets, i < nr_buckets_in_use ? nr_buckets_in_use : nr_buckets_in_use+1, left-1, printsol, maxmul);
            buckets[i] += left;
        }
    return found;
}

void checkSet(long n, long maxmul, long basemul)
{
    bool all = true;
    for (int nr_buckets = n; all && nr_buckets > 1; nr_buckets--)
    {
        for (int j = 0; j < nr_buckets; j++)
            buckets[j] = basemul / nr_buckets;
        all = knapsack(nr_buckets, 0, maxmul, false, maxmul);
    }

    if (all)
    {
        found_set = true;
        printf("set: ");
        int maxset = 1;
        for (int j = 1; j <= maxmul; j++)
            if (selected[j])
                maxset = j;
        printf("%d, .., %d except for", 1, maxset);
        for (int j = 1; j <= maxset; j++)
            if (!selected[j])
                printf(" %d", j);
        printf("\n");
    }                
}

void generateSets(long i, long left, long nn, long n, long maxmul, long basemul, bool exact)
{
    if (exact && nn < 0)
        return;
    if (i == 0)
    {
        if (left == 0 && nn <= 0)
            checkSet(n, maxmul, basemul);
        return;
    }
    if (left > sumUpTo(i))
        return;
    if (nn > i)
        return;
    generateSets(i-1, left, nn, n, maxmul, basemul, exact);
    if (found_set)
        return;
    if (left >= i)
    {
        selected[i] = true;
        generateSets(i-1, left - i, nn-1, n, maxmul, basemul, exact);
        selected[i] = false;
    }
}

int main(int argc, char *argv[])
{
    long base = 1;
    
    for (long n = 1; n < 17; n++)
    {
        base = lcm(base, n);
        long max = base / n;
        printf("%ld : %ld %ld\n", n, base, max);
        
        long multiple = 1;
        while (sumUpTo(max * multiple) < base)
            multiple++;
        if (multiple > 1)
            printf("  need %ld %ld\n", multiple, base * multiple);

        // Generate all sets
        found_set = false;
        for (; multiple < 5 && !found_set; multiple++)
        {
            long maxmul = max * multiple;
            int m = 1;
            while (sumUpTo(m) < base)
                m++;
            m += 10;
            printf("try %d (%d)\n", maxmul, m);
            if (m <= MAX_NR_SET)
            {
                for (int i = 1; i <= m; i++)
                    selected[i] = false;
                generateSets(m, base * multiple, n*2-1, n, m, base * multiple, false);
            }
        }
    }
    
    return 0;
}