Cerinţa

Se citește un număr natural nenul n. Să se afişeze, în ordine lexicografică, toate submulțimile nevide ale mulţimii {1,2,..,n} pentru care diferența dintre oricare două elemente este mai mare decât 1.

Date de intrare

Fişierul de intrare submultimi1.in conţine pe prima linie numărul n.

Date de ieşire

Fişierul de ieşire submultimi1.out va conţine pe fiecare linie câte o submulțime, elementele unei submulțimi fiind separate printr-un spațiu.

Restricţii şi precizări

• 1 ≤ n ≤ 10
• elementele fiecărei submulțimi vor fi afișate în ordine crescătoare

Exemplu

submultimi1.in

5

submultimi1.out

1 
1 3 
1 3 5 
1 4 
1 5 
2 
2 4 
2 5 
3 
3 5 
4 
5 

#include <bits/stdc++.h>
using namespace std;
ifstream cin("submultimi1.in");
ofstream cout("submultimi1.out");
int n , x[11];
int mic(int l)
{
    for(int i = 2 ; i <= l ; ++i)
        if(x[i] - x[i - 1] < 2) return 0;
    return 1;
}
void afis(int l)
{
    for(int i = 1 ; i <= l ; ++i)
        cout << x[i] << ' ';
    cout << endl;
}
void backt(int k)
{
    for(int i = x[k-1] + 1 ; i <= n ; ++i)
    {
        x[k] = i;
        if(mic(k)) afis(k);
        backt(k+1);
    }
}

int main()
{
    cin >> n;
    backt(1);
    return 0;
}