permutari_pfp

#include <iostream>
#define NR 12
using namespace std;
int n,x[NR],m,v[NR];

void init(int k)
{
    x[k]=0;
}

bool succesor(int k)
{
    if(x[k]<m)
        return true;
    else
        return false;
}

bool continuare(int k)
{
    for(int i=1;i<=k-1;++i) /// Valorile sa fie distincte
        if(x[k]==x[i])
            return false;
    return true;
}

bool solutie(int k)
{
    if(k==m+1)
        return true;
    else
        return false;
}

void afisare()
{
    int j=0;
    for(int i=1;i<=n;++i)
        if(i%2==0)
            cout<<i<<' ';
        else
            cout<<v[x[++j]]<<' ';
    cout<<'\n';
}

void backtracking() /// Generam permutarile multimii {1,2,...,n}
{
int k=1;
init(k);
while(k)
    if(solutie(k))
    {
        afisare();
        --k;
    }
    else
        if(succesor(k))
        {
            ++x[k];
            if(continuare(k))
                ++k;
        }
        else
        {
            init(k);
            --k;
        }
}

int main()
{
    cin>>n;
    m=0;
    for(int i=1;i<=n;++i)
        if(i%2)
            v[++m]=i;
    backtracking();
    return 0;
}