Backtracking

//                                           --------GENERARE PERMUTARI---------
#include <iostream>

using namespace std;

int n,s[100];

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

int succesor(int k)
{
    if(s[k]<n)
    {
        s[k]++;
        return 1;
    }
    return 0;
}

int valid(int k)//sa nu se afle sk de 2 ori in solutie
{
    int i;
    for(i=1;i<k;i++)
        if(s[i]==s[k])
            return 0;
    return 1;
}

int solutie(int k)//sa aiba nr acelasi nr de elem
{
    if(k==n)
        return 1;
    return 0;
}

void tipar(int k)
{
    int i;
    for(i=1;i<=k;i++)
        cout<<s[i]<<" ";
    cout<<endl;
}

void bkt(int k)
{
    int as,ev;
    init(k);
    while(k>0)
    {
        do
        {
            as=succesor(k);
            if(as==1)
                ev=valid(k);
        }while(as==1 && ev==0);
        if(as==1)
            if(solutie(k)==1)
                tipar(k);
        else
        {
            k++;
            init(k);
        }
        else
            k--;
    }
}

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

//                                 --------1 PE PRIMA POZITIE SI N PE ULTIMA---------

#include <iostream>

using namespace std;

int n,s[100];

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

int succesor(int k)
{
    if(s[k]<n)
    {
        s[k]++;
        return 1;
    }
    return 0;
}

int valid(int k)
{
    int i;
    if(k==1)
        if(s[k]!=1)
            return 0;
    if(k==n)
        if(s[k]!=n)
            return 0;
    for(i=1;i<k;i++)
        if(s[i]==s[k])
            return 0;
    return 1;
}

int solutie(int k)
{
    if(k==n)
        return 1;
    return 0;
}

void tipar(int k)
{
    int i;
    for(i=1;i<=k;i++)
        cout<<s[i]<<" ";
    cout<<endl;
}

void bkt(int k)
{
    int as,ev;
    init(k);
    while(k>0)
    {
        do
        {
            as=succesor(k);
            if(as==1)
                ev=valid(k);
        }while(as==1 && ev==0);
        if(as==1)
            if(solutie(k)==1)
                tipar(k);
        else
        {
            k++;
            init(k);
        }
        else
            k--;
    }
}

int main()
{
    cin>>n;
    bkt(1);

    return 0;
}

//                                 --------NU EXISTA 2 VALORI ALATURATE CONSECUTIVE---------

#include <iostream>

using namespace std;

int n,i,s[100];

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

int succesor(int k)
{
    if(s[k]<n)
    {
        s[k]++;
        return 1;
    }
    return 0;
}

int valid(int k)
{
    int i;
    if(k>1)
        if(s[k]==s[k-1]+1 || s[k]==s[k-1]-1)
            return 0;
    for(i=1;i<k;i++)
        if(s[i]==s[k])
            return 0;
    return 1;
}

int solutie(int k)
{
    if(k==n)
        return 1;
    return 0;
}

void tipar(int k)
{
    int i;
    for(i=1;i<=k;i++)
        cout<<s[i]<<" ";
    cout<<endl;
}

void bkt(int k)
{
    int as,ev;
    init(k);
    while(k>0)
    {
        do
        {
            as=succesor(k);
            if(as==1)
                ev=valid(k);
        }while(as==1 && ev==0);
        if(as==1)
            if(solutie(k)==1)
                tipar(k);
        else
        {
            k++;
            init(k);
        }
        else
            k--;
    }
}

int main()
{
    cin>>n;
    bkt(1);

    return 0;
}

//                                 --------NU EXISTA PERMUTARE CU P[I]=I---------

#include <iostream>

using namespace std;

int n,s[100];

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

int succesor(int k)
{
    if(s[k]<n)
    {
        s[k]++;
        return 1;
    }
    return 0;
}

int valid(int k)
{
    int i;
    if(s[k]==k)
        return 0;
    for(i=1;i<k;i++)
        if(s[i]==s[k])
            return 0;
    return 1;
}

int solutie(int k)
{
    if(k==n)
        return 1;
    return 0;
}

void tipar(int k)
{
    int i;
    for(i=1;i<=k;i++)
        cout<<s[i]<<" ";
    cout<<endl;
}

void bkt(int k)
{
    int as,ev;
    init(k);
    while(k>0)
    {
        do
        {
            as=succesor(k);
            if(as==1)
                ev=valid(k);
        }while(as==1 && ev==0);
        if(as==1)
            if(solutie(k)==1)
                tipar(k);
        else
        {
            k++;
            init(k);
        }
        else
            k--;
    }
}

int main()
{
    cin>>n;
    bkt(1);

    return 0;
}

//                                 --------PE PRIMA POZITIE E N SI PE ULTIMA E N+P---------

#include <iostream>

using namespace std;

int n,s[100],p;

void init(int k)
{
    s[k]=n-1;
}

int succesor(int k)
{
    if(s[k]<n+p)
    {
        s[k]++;
        return 1;
    }
    return 0;
}

int valid(int k)
{
    int i;
    if(k==1)
        if(s[k]!=n)
            return 0;
    if(k>1)
        if(s[k]<=s[k-1])
            return 0;
    return 1;
}

int solutie(int k)
{
    if(s[k]==n+p)
        return 1;
    return 0;
}

void tipar(int k)
{
    int i;
    for(i=1;i<=k;i++)
        cout<<s[i]<<" ";
    cout<<endl;
}

void bkt(int k)
{
    int as,ev;
    init(k);
    while(k>0)
    {
        do
        {
            as=succesor(k);
            if(as==1)
                ev=valid(k);
        }while(as==1 && ev==0);
        if(as==1)
            if(solutie(k)==1)
                tipar(k);
        else
        {
            k++;
            init(k);
        }
        else
            k--;
    }
}

int main()
{
    cin>>n>>p;
    bkt(1);

    return 0;
}

//                                 --------2 NU ESTE INSCRIPTIONAT INAINTE DE 1---------

#include <iostream>

using namespace std;

int n,s[100];

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

int succesor(int k)
{
    if(s[k]<n)
    {
        s[k]++;
        return 1;
    }
    return 0;
}

int valid(int k)
{
    int i;
    if(s[k]==1)
        for(i=1;i<k;i++)
            if(s[i]==2)
                return 0;
    for(i=1;i<k;i++)
        if(s[i]==s[k])
            return 0;
    return 1;
}

int solutie(int k)
{
    if(k==n)
        return 1;
    return 0;
}

void tipar(int k)
{
    int i;
    for(i=1;i<=k;i++)
        cout<<s[i]<<" ";
    cout<<endl;
}

void bkt(int k)
{
    int as,ev;
    init(k);
    while(k>0)
    {
        do
        {
            as=succesor(k);
            if(as==1)
                ev=valid(k);
        }while(as==1 && ev==0);
        if(as==1)
            if(solutie(k)==1)
                tipar(k);
        else
        {
            k++;
            init(k);
        }
        else
            k--;
    }
}

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

//                                 --------DRAPELUL CU 3 CULORI NU ARE VOIE SA AIBA IN MIJLOC 1 SAU 4---------

#include <iostream>

using namespace std;

int n,s[100];

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

int succesor(int k)
{
    if(s[k]<n)
    {
        s[k]++;
        return 1;
    }
    return 0;
}

int valid(int k)
{
    int i;
    if(k==2)
        if(s[k]==1 || s[k]==4)
            return 0;
    for(i=1;i<k;i++)
        if(s[i]==s[k])
            return 0;
    return 1;
}

int solutie(int k)
{
    if(k==3)
        return 1;
    return 0;
}

void tipar(int k)
{
    int i;
    for(i=1;i<=k;i++)
    {
        if(s[i]==1)
            cout<<"galben ";
        if(s[i]==2)
            cout<<"portocaliu ";
        if(s[i]==3)
            cout<<"rosu ";
        if(s[i]==4)
            cout<<"visiniu ";
        if(s[i]==5)
            cout<<"verde ";
        if(s[i]==6)
            cout<<"albastru ";
    }
    cout<<endl;
}

void bkt(int k)
{
    int as,ev;
    init(k);
    while(k>0)
    {
        do
        {
            as=succesor(k);
            if(as==1)
                ev=valid(k);
        }while(as==1 && ev==0);
        if(as==1)
            if(solutie(k)==1)
                tipar(k);
        else
        {
            k++;
            init(k);
        }
        else
            k--;
    }
}

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

//                                 --------NU EXISTA 2 VALORI ALATURATE CONSECUTIVE---------

#include <iostream>

using namespace std;

int n,i,s[100],v[100];

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

int succesor(int k)
{
    if(s[k]<n)
    {
        s[k]++;
        return 1;
    }
    return 0;
}

int valid(int k)
{
    int i;
    for(i=1;i<k;i++)
        if(s[i]==s[k])
            return 0;
    return 1;
}

int solutie(int k)
{
    if(k==n)
        return 1;
    return 0;
}

void tipar(int k)
{
    int i;
    for(i=1;i<=k;i++)
        cout<<v[s[i]]<<" ";
    cout<<endl;
}

void bkt(int k)
{
    int as,ev;
    init(k);
    while(k>0)
    {
        do
        {
            as=succesor(k);
            if(as==1)
                ev=valid(k);
        }while(as==1 && ev==0);
        if(as==1)
            if(solutie(k)==1)
                tipar(k);
        else
        {
            k++;
            init(k);
        }
        else
            k--;
    }
}

int main()
{
    cin>>n;
    for(i=1;i<=n;i++)
        cin>>v[i];
    bkt(1);
    return 0;
}

//                                 --------NU EXISTA 2 VALORI ALATURATE CU ACEEASI PARITATE---------

#include <iostream>

using namespace std;

int n,i,s[100],v[100];

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

int succesor(int k)
{
    if(s[k]<n)
    {
        s[k]++;
        return 1;
    }
    return 0;
}

int valid(int k)
{
    int i;
    if(k>1)
        if(v[s[k-1]]%2==v[s[k]]%2)
            return 0;
    for(i=1;i<k;i++)
        if(s[i]==s[k])
            return 0;
    return 1;
}

int solutie(int k)
{
    if(k==n)
        return 1;
    return 0;
}

void tipar(int k)
{
    int i;
    for(i=1;i<=k;i++)
        cout<<v[s[i]]<<" ";
    cout<<endl;
}

void bkt(int k)
{
    int as,ev;
    init(k);
    while(k>0)
    {
        do
        {
            as=succesor(k);
            if(as==1)
                ev=valid(k);
        }while(as==1 && ev==0);
        if(as==1)
            if(solutie(k)==1)
                tipar(k);
        else
        {
            k++;
            init(k);
        }
        else
            k--;
    }
}

int main()
{
    cin>>n;
    for(i=1;i<=n;i++)
        cin>>v[i];
    bkt(1);
    return 0;
}

//                                 --------GENERARE ARANJAMENTE---------

#include <iostream>

using namespace std;

int n,s[100],p;

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

int succesor(int k)
{
    if(s[k]<n)
    {
        s[k]++;
        return 1;
    }
    return 0;
}

int valid(int k)
{
    int i;
    for(i=1;i<k;i++)
        if(s[i]==s[k])
            return 0;
    return 1;
}

int solutie(int k)
{
    if(k==p)
        return 1;
    return 0;
}

void tipar(int k)
{
    int i;
    for(i=1;i<=k;i++)
        cout<<s[i]<<" ";
    cout<<endl;
}

void bkt(int k)
{
    int as,ev;
    init(k);
    while(k>0)
    {
        do
        {
            as=succesor(k);
            if(as==1)
                ev=valid(k);
        }while(as==1 && ev==0);
        if(as==1)
            if(solutie(k)==1)
                tipar(k);
        else
        {
            k++;
            init(k);
        }
        else
            k--;
    }
}

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

//                                 --------TOATE NR DE N CIFRE DIVIZIBILE CU 3---------

#include <iostream>

using namespace std;

int n,i,s1,s[100];

void init(int k)
{
    s[k]=-1;
}

int succesor(int k)
{
    if(s[k]<9)
    {
        s[k]++;
        return 1;
    }
    return 0;
}

int valid(int k)
{
    int i;
    if(k==1)
        if(s[k]==0)
            return 0;
    for(i=1;i<k;i++)
        if(s[i]==s[k])
            return 0;
    return 1;
}

int solutie(int k)
{
    if(k==n)
        return 1;
    return 0;
}

int suma(int k)
{
    int s1=0;
    for(i=1;i<=k;i++)
         s1+=s[i];
    return s1;
}

void tipar(int k)
{
    int i;
    if(suma(k)%3==0)
    {
        for(i=1;i<=k;i++)
            cout<<s[i]<<" ";
        cout<<endl;
    }
}

void bkt(int k)
{
    int as,ev;
    init(k);
    while(k>0)
    {
        do
        {
            as=succesor(k);
            if(as==1)
                ev=valid(k);
        }while(as==1 && ev==0);
        if(as==1)
            if(solutie(k)==1)
                tipar(k);
        else
        {
            k++;
            init(k);
        }
        else
            k--;
    }
}

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

//                                 --------CIFRELE IN ORDINE CRESCATOARE CARE CONTIN 3---------

#include <iostream>

using namespace std;

int n,s[100];

void init(int k)
{
    s[k]=-1;
}

int succesor(int k)
{
    if(s[k]<n)
    {
        s[k]++;
        return 1;
    }
    return 0;
}

int valid(int k)
{
    int i;
    if(k==1)
        if(s[k]==0)
            return 0;
    if(k>1)
        if(s[k-1]>=s[k])
            return 0;
    return 1;
}

int solutie(int k)
{
    if(k==n)
        return 1;
    return 0;
}

int verific(int k)
{
    int i;
    for(i=1;i<=k;i++)
        if(s[i]==3)
            return 1;
    return 0;
}

void tipar(int k)
{
    int i;
    if(verific(k)==1)
    {
        for(i=1;i<=k;i++)
            cout<<s[i]<<" ";
        cout<<endl;
    }
}

void bkt(int k)
{
    int as,ev;
    init(k);
    while(k>0)
    {
        do
        {
            as=succesor(k);
            if(as==1)
                ev=valid(k);
        }while(as==1 && ev==0);
        if(as==1)
            if(solutie(k)==1)
                tipar(k);
        else
        {
            k++;
            init(k);
        }
        else
            k--;
    }
}

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

//                                 --------TOATE NR CARE NU CONTIN 3 CIFRE PARE SAU 3 CIFRE IMPARE ALATURATE---------

#include <iostream>

using namespace std;

int n,s[100];

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

int succesor(int k)
{
    if(s[k]<n)
    {
        s[k]++;
        return 1;
    }
    return 0;
}

int valid(int k)
{
    int i;
    if(k==1)
        if(s[k]==0)
            return 0;
    if(s[k-2]%2==s[k-1]%2 && s[k-1]%2==s[k]%2)
        return 0;
    return 1;
}

int solutie(int k)
{
    if(k==n)
        return 1;
    return 0;
}

void tipar(int k)
{
    int i;
    for(i=1;i<=k;i++)
        cout<<s[i]<<" ";
    cout<<endl;
}

void bkt(int k)
{
    int as,ev;
    init(k);
    while(k>0)
    {
        do
        {
            as=succesor(k);
            if(as==1)
                ev=valid(k);
        }while(as==1 && ev==0);
        if(as==1)
            if(solutie(k)==1)
                tipar(k);
        else
        {
            k++;
            init(k);
        }
        else
            k--;
    }
}

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

//                                 --------GENERARE COMBINARI---------

#include <iostream>

using namespace std;

int n,p,s[100];

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

int succesor(int k)
{
    if(s[k]<n)
    {
        s[k]++;
        return 1;
    }
    return 0;
}

int valid(int k)
{
    int i;
    if(k>1)
        if(s[k-1]>=s[k])
            return 0;
    return 1;
}

int solutie(int k)
{
    if(k==p)
        return 1;
    return 0;
}

void tipar(int k)
{
    int i;
    for(i=1;i<=k;i++)
        cout<<s[i]<<" ";
    cout<<endl;
}

void bkt(int k)
{
    int as,ev;
    init(k);
    while(k>0)
    {
        do
        {
            as=succesor(k);
            if(as==1)
                ev=valid(k);
        }while(as==1 && ev==0);
        if(as==1)
            if(solutie(k)==1)
                tipar(k);
        else
        {
            k++;
            init(k);
        }
        else
            k--;
    }
}

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

//                                 --------------2 SI 4 SA NU FIE IN ACELASI BUCHET---------------

#include <iostream>

using namespace std;

int n,p,s[100];

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

int succesor(int k)
{
    if(s[k]<n)
    {
        s[k]++;
        return 1;
    }
    return 0;
}

int valid(int k)
{
    int i;
    if(k>1)
        if(s[k-1]>=s[k])
            return 0;
    if(s[k]==2)
        for(i=1;i<k;i++)
            if(s[i]==4)
                return 0;
    if(s[k]==4)
        for(i=1;i<k;i++)
            if(s[i]==2)
                return 0;
    return 1;
}

int solutie(int k)
{
    if(k==p)
        return 1;
    return 0;
}

void tipar(int k)
{
    int i;
    for(i=1;i<=k;i++)
    {
        if(s[i]==1)
            cout<<"brandusa ";
        if(s[i]==2)
            cout<<"iasomie ";
        if(s[i]==3)
            cout<<"lalea ";
        if(s[i]==4)
            cout<<"liliac ";
        if(s[i]==5)
            cout<<"margareta ";
    }
    cout<<endl;
}

void bkt(int k)
{
    int as,ev;
    init(k);
    while(k>0)
    {
        do
        {
            as=succesor(k);
            if(as==1)
                ev=valid(k);
        }while(as==1 && ev==0);
        if(as==1)
            if(solutie(k)==1)
                tipar(k);
        else
        {
            k++;
            init(k);
        }
        else
            k--;
    }
}

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

//                                 --------GENERAREA SUBMULTIMILOR UNEI MULTIMI---------

#include <iostream>

using namespace std;

int n,s[100];

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

int succesor(int k)
{
    if(s[k]<2)
    {
        s[k]++;
        return 1;
    }
    return 0;
}

int valid(int k)
{
    return 1;
}

int solutie(int k)
{
    if(k==n)
        return 1;
    return 0;
}

void tipar(int k)
{
    int i;
    for(i=1;i<=k;i++)
        if(s[i]==1)
            cout<<i<<" ";
    cout<<endl;
}

void bkt(int k)
{
    int as,ev;
    init(k);
    while(k>0)
    {
        do
        {
            as=succesor(k);
            if(as==1)
                ev=valid(k);
        }while(as==1 && ev==0);
        if(as==1)
            if(solutie(k)==1)
                tipar(k);
        else
        {
            k++;
            init(k);
        }
        else
            k--;
    }
}

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

//                                 --------PARTITILE UNUI NR A---------

#include <iostream>

using namespace std;

int n,s[100];

int suma(int k)
{
    int i,s1=0;
    for(i=1;i<=k;i++)
        s1+=s[i];
    return s1;
}

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

int succesor(int k)
{
    if(s[k]<n && suma(k)<n)
    {
        s[k]++;
        return 1;
    }
    return 0;
}

int valid(int k)
{
    int i;
    return 1;
}

int solutie(int k)
{
    if(suma(k)==n)
        return 1;
    return 0;
}

void tipar(int k)
{
    int i;
    for(i=1;i<=k;i++)
        cout<<s[i]<<" ";
    cout<<endl;
}

void bkt(int k)
{
    int as,ev;
    init(k);
    while(k>0)
    {
        do
        {
            as=succesor(k);
            if(as==1)
                ev=valid(k);
        }while(as==1 && ev==0);
        if(as==1)
            if(solutie(k)==1)
                tipar(k);
        else
        {
            k++;
            init(k);
        }
        else
            k--;
    }
}
 int main()
{
    cin>>n;
    bkt(1);

    return 0;
}

//                                 --------PARTITILE UNUI NR B---------

#include <iostream>

using namespace std;

int n,s[100];

int suma(int k)
{
    int i,s1=0;
    for(i=1;i<=k;i++)
        s1+=s[i];
    return s1;
}

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

int succesor(int k)
{
    if(s[k]<n && suma(k)<n)
    {
        s[k]++;
        return 1;
    }
    return 0;
}

int valid(int k)
{
    int i;
    if(k>1)
        if(s[k]<s[k-1])
            return 0;
    return 1;
}

int solutie(int k)
{
    if(suma(k)==n)
        return 1;
    return 0;
}

void tipar(int k)
{
    int i;
    for(i=1;i<=k;i++)
        cout<<s[i]<<" ";
    cout<<endl;
}

void bkt(int k)
{
    int as,ev;
    init(k);
    while(k>0)
    {
        do
        {
            as=succesor(k);
            if(as==1)
                ev=valid(k);
        }while(as==1 && ev==0);
        if(as==1)
            if(solutie(k)==1)
                tipar(k);
        else
        {
            k++;
            init(k);
        }
        else
            k--;
    }
}
 int main()
{
    cin>>n;
    bkt(1);

    return 0;
}

//                                 --------PARTITILE UNUI NR C---------

#include <iostream>

using namespace std;

int n,s[100];

int suma(int k)
{
    int i,s1=0;
    for(i=1;i<=k;i++)
        s1+=s[i];
    return s1;
}

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

int succesor(int k)
{
    if(s[k]<n && suma(k)<n)
    {
        s[k]++;
        return 1;
    }
    return 0;
}

int valid(int k)
{
    int i;
    if(k>1)
        if(s[k]<s[k-1])
            return 0;
    for(i=1;i<k;i++)
        if(s[i]==s[k])
            return 0;
    return 1;
}

int solutie(int k)
{
    if(suma(k)==n)
        return 1;
    return 0;
}

void tipar(int k)
{
    int i;
    for(i=1;i<=k;i++)
        cout<<s[i]<<" ";
    cout<<endl;
}

void bkt(int k)
{
    int as,ev;
    init(k);
    while(k>0)
    {
        do
        {
            as=succesor(k);
            if(as==1)
                ev=valid(k);
        }while(as==1 && ev==0);
        if(as==1)
            if(solutie(k)==1)
                tipar(k);
        else
        {
            k++;
            init(k);
        }
        else
            k--;
    }
}
 int main()
{
    cin>>n;
    bkt(1);

    return 0;
}

//                                 --------PROBLEMA CELOR N DAME---------

#include <iostream>
#include <cmath>

using namespace std;

int n,s[100];

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

int succesor(int k)
{
    if(s[k]<n)
    {
        s[k]++;
        return 1;
    }
    return 0;
}

int valid(int k)
{
    int i;
    for(i=1;i<k;i++)
    {
        if(s[i]==s[k])
            return 0;
        if(abs(s[k]-s[i])==k-i)
            return 0;
    }
    return 1;
}

int solutie(int k)
{
    if(k==n)
        return 1;
    return 0;
}

void tipar(int k)
{
    int i,j;
    for(i=1;i<=k;i++)
    {
        for(j=1;j<=k;j++)
            if(s[i]==j)
                cout<<"R";
            else
                cout<<"*";
        cout<<endl;
    }
    cout<<endl;
}

void bkt(int k)
{
    int as,ev;
    init(k);
    while(k>0)
    {
        do
        {
            as=succesor(k);
            if(as==1)
                ev=valid(k);
        }while(as==1 && ev==0);
        if(as==1)
            if(solutie(k)==1)
                tipar(k);
        else
        {
            k++;
            init(k);
        }
        else
            k--;
    }
}
 int main()
{
    cin>>n;
    bkt(1);

    return 0;
}

//                                 --------COLORAREA HARTILOR---------

#include <iostream>
#include <fstream>

using namespace std;

ifstream f("harta.txt");

int n,s[100],a[20][20];

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

int succesor(int k)
{
    if(s[k]<4)
    {
        s[k]++;
        return 1;
    }
    return 0;
}

int valid(int k)
{
    int i;
    for(i=1;i<k;i++)
        if(a[i][k]==1 && s[i]==s[k])
            return 0;
    return 1;
}

int solutie(int k)
{
    if(k==n)
        return 1;
    return 0;
}

void tipar(int k)
{
    int i;
    for(i=1;i<=k;i++)
        if(s[i]==1)
            cout<<i<<" ";
    cout<<endl;
}

void bkt(int k)
{
    int as,ev;
    init(k);
    while(k>0)
    {
        do
        {
            as=succesor(k);
            if(as==1)
                ev=valid(k);
        }while(as==1 && ev==0);
        if(as==1)
            if(solutie(k)==1)
                tipar(k);
        else
        {
            k++;
            init(k);
        }
        else
            k--;
    }
}
 int main()
{
    int i,j;
    f>>n;
    for(i=1;i<=n;i++)
        for(j=1;j<=n;j++)
            f>>a[i][j];
    bkt(1);

    return 0;
}

//                                 --------MULTIMILE ELEMETELOR VECTORULUI CU SUMA S---------

#include <iostream>

using namespace std;

int n,s[100],v[100],S;

int suma(int k)
{
    int i,s1=0;
    for(i=1;i<=k;i++)
        s1+=v[s[i]];
    return s1;
}

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

int succesor(int k)
{
    int i,s1=0;
    for(i=1;i<k;i++)
        s1+=v[s[i]];
    if(s[k]<n && s1<S)
    {
        s[k]++;
        return 1;
    }
    return 0;
}

int valid(int k)
{
    int i;
    if(k>1)
        if(s[k-1]>s[k])
            return 0;
    for(i=1;i<k;i++)
        if(s[i]==s[k])
            return 0;
    return 1;
}

int solutie(int k)
{
    if(suma(k)==S)
        return 1;
    return 0;
}

void tipar(int k)
{
    int i;
    for(i=1;i<=k;i++)
        cout<<v[s[i]]<<" ";
    cout<<endl;
}

void bkt(int k)
{
    int as,ev;
    init(k);
    while(k>0)
    {
        do
        {
            as=succesor(k);
            if(as==1)
                ev=valid(k);
        }while(as==1 && ev==0);
        if(as==1)
            if(solutie(k)==1)
                tipar(k);
        else
        {
            k++;
            init(k);
        }
        else
            k--;
    }
}
 int main()
{
    cin>>n>>S;
    for(int i=1;i<=n;i++)
        cin>>v[i];
    bkt(1);

    return 0;
}