Cerința

Se dă un număr natural n. Determinați, în ordine lexicografică, toate modalitățile de a-l scrie pe n ca sumă de numere naturale ordonate strict crescător astfel încât diferența dintre doi termeni consecutivi ai sumei să fie cel mult 2.

Date de intrare

Programul citește de la tastatură numărul n.

Date de ieșire

Programul va afișa pe ecran pe fiecare linie câte un șir de numere naturale ordonate strict crescător, separate prin câte un spațiu. Suma numerelor din fiecare șir este n, iar diferența dintre oricare doi termeni consecutivi este cel mult 2. Șirurile vor fi afișate în ordine lexicografică.

Restricții și precizări

• 1 ≤ n ≤ 300

Exemplu

Intrare

21

Ieșire

1 2 3 4 5 6 
1 2 4 6 8 
1 3 4 6 7 
2 3 4 5 7 
3 4 6 8 
3 5 6 7 
5 7 9 
6 7 8 
10 11 
21 

#include <bits/stdc++.h>
using namespace std;

int n , x[301];

void afisare(int k)
{
    for(int i = 1 ; i <= k ; i++)
        cout << x[i] << " ";
    cout << '\n';
}

void back(int k , int sp)
{
    for(int i = x[k - 1] + 1 ; i <= n - sp ; i++)
    {
        x[k] = i;
        if(k == 1 || (x[k] - x[k - 1] <= 2 && x[k] > x[k - 1]))
        {
            sp += x[k];
            if(sp <= n)
                if(sp == n) afisare(k);
                else back(k + 1 , sp);
            sp -= x[k];
        }
    }
}

int main()
{
    cin >> n;
    back(1 , 0);
}