Zeros and ones (1)

Go to the Jutge statement of the problem

Write a backtracking program to print all the combinations of z zeros and o ones such that z + o = n, for a given n.

Input: Input consists of a natural number n > 0.

Output: Print all the combinations of z zeros and o ones such that z + o = n, one per line and in lexicographical order.

Although a backtracking program is not really necessary to solve this exercise, implement it anyway for the sake of practice.

Hint

Revise the basic template for backtracking

A possible C++ code to start the problem

// Zeros and ones (1)
#include<iostream>
#include<vector>

using namespace std;

void write (const vector<bool> & v){
    cout << v[0];
    int n = v.size();
    for (int i = 1; i < n; ++i)
        cout << " " << v[i];
    cout << endl;
}

void backtrack(vector<bool>& sol, int k){
 //basic backtracking
}

int main(){
    int n;
    cin >> n;
    vector<bool> sol(n,false);
    backtrack(sol, 0);
}

A possible solution

// Zeros and ones (1)
#include<iostream>
#include<vector>

using namespace std;

void write (const vector<bool> & v){
    cout << v[0];
    int n = v.size;
    for (int i = 1; i < n; ++i)
        cout << " " << v[i];
    cout << endl;
}

void backtrack(vector<bool>& sol, int k){
    int n = sol.size();
    if (k == n) write(sol);
    else{
        sol[k] = false;
        backtrack(sol, k+1);
        sol[k] = true;
        backtrack(sol, k+1);
    }
}

int main(){
    int n;
    cin >> n;
    vector<bool> sol(n, false);
    backtrack(sol, 0);
}