Đệ quy quay lui- Phát sinh dãy số nhị phân

class BackTracking

{

public:

    int n;

    vector< vector<int> > ketqua;

    vector<int>tem;

    vector<int>GhiNhanViTri;

    void ps()

    {

        GhiNhanViTri.assign(n,0);

    }

    void xoa(vector<int> & vd, int vt)

    {

        vector<int>::iterator it=vd.begin();

        it=it+vt;

        vd.erase(it,vd.end());

    }

    void DayNhiPhan(int i)

    {

        for(int j=0;j<=1;j++)   

        {

            if(GhiNhanViTri[i]==0)

            {

                xoa(tem,i);

                tem.push_back(j);;

            }

            if(i==n-1)

            {

                ketqua.push_back(tem);

               

            }

            else

            {

                GhiNhanViTri.push_back(1);

                DayNhiPhan(i+1);

                GhiNhanViTri.push_back(0);

            }

        }

    }

};

int _tmain(int argc, _TCHAR* argv[])

{  

    BackTracking ob;

    ob.n=10;

    ob.ps();

    ob.DayNhiPhan(0);

}

Thay vì dùng mảng ta dùng vector để thấy nhiều cái tiện lợi của nó.

Phương Pháp Sinh-Phát sinh dãy số nhị phân

Cho số n, hãy phát sinh ra các dãy nhị phân có chiều dài đúng bằng n.
Ví dụ:
n=2 các dãy nhị phân là:  00  01  10 11
n=3 các dãy nhị phân tương ứng là :000 001  010   011  100   101   110  111

  Đi từ cuối dãy nếu gặp số 0 thì đổi thành 1 và những số 1 đằng sau biến thanh số 0   

#include<iostream>
#include<stack>
#include<queue>
#include<algorithm>
using namespace std;
vector< vector<int> >PhatSinhdayNhiPhan(int n)
{
    vector< vector<int> > tem;
    vector<int> bandau(n,0);
    vector<int> cuoicung(n,1);
    int size=bandau.size();
    tem.push_back(bandau);
    while(!equal(bandau.begin(),bandau.end(), cuoicung.begin()) )
    {      
        for(int i=size-1;i>=0;i--)
        {
            if(bandau[i]==0)
            {
                bandau[i]=1;
                for(int j=i+1;j<size;j++)
                {
                    bandau[j]=0;
                }
                break;
            }
        }
        tem.push_back(bandau);      
    }
    return tem;
}

Cây Nhị Phân- Duyệt Sâu Và Duyệt Rộng