Cerința

Se dă un număr natural n. Afișați în ordine lexicografică toate secvențele de cifre binare care au atâtea cifre de 0 și atâtea cifre de 1 câte are reprezentarea binară a lui n.

Date de intrare

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

Date de ieșire

Programul va afișa pe ecran combinațiile de cifre binare cerute, câte una pe fiecare rând.

Restricții și precizări

• 1 ≤ n ≤ 2.000.000

Exemplu

Intrare

17

Ieșire

00011
00101
00110
01001
01010
01100
10001
10010
10100
11000

Explicație

Numărul n are reprezentarea binară 10001, deci se generează combinațiile cu 3 cifre de 0 si 2 cifre de 1.

#include <bits/stdc++.h>

using namespace std;

int n , m , x[30] , p[30] , cnt , a[30] , c1 , c0;

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

int valid(int k)
{
    int c00 = 0 , c11 = 0;
    for(int i = 1 ; i <= k ; i++)
        if(x[i] == 0) c00++;
        else c11++;
    if(c00 <= c0 && c11 <= c1) return 1;
    else return 0;
}

void back(int k)
{
    for(int i = 0 ; i <= 1 ; i++)
    {
        x[k] = i;
        if(valid(k))
        {
            if(k == cnt) afisare();
            else back(k + 1);
        }
    }
}

int main()
{
    cin >> n;
    while(n != 0)
    {
        a[++cnt] = n % 2;
        n /= 2;
    }
    for(int i = 1 ; i <= cnt ; i++)
    {
        if(a[i] == 0) c0++;
        else c1++;
    }
    back(1);
}