UAV 729 The Hamming Distance Backtracking Problem

• Tweet
• 
• Email

• Tweet
• 
• Email

This problem simply states that we have to print all permutation of binary number of length N with M number of 1’s. Let us see the below example test case.

Sample Input
1
4 2
Sample Output
0011
0101
0110
1001
1010
1100

Test case explanation
N is 4  ( it means 4 length of binary number)
M is 2 ( it means number of 1’s in binary number)
Observation:
Look at the first output ( 0011) , the last two digit of first output is 1 1. The next output is the all combinations of first output.

How to solve:
(1) take a string of length N , filled with 0.
(2) Append 1 1 to the end of the string.
(3) Print all combinations of string ( achieved at step 2).

Problem link:
https://uva.onlinejudge.org/index.php?option=onlinejudge&page=show_problem&problem=670

Solution:

#include<algorithm>
#include<cstdio>
#include<iostream>
 
using namespace std;
 
int T=0, N=0, M=0;
string s;
 
int main() {
    
    // read number of test case 
    cin>>T;
    for(int test=0; test < T; test++) 
    {
        // read length of binary number(N) and number of(M) 1's
        cin>>N>>M;
        
        // make first string 
        s = "";
        for(int i = 0; i < N; i++) {
            if(i < N - M)
                s += '0';
            else
                s += '1';
        }
        // permutation of string s
        do
        {
          cout << s << endl;
        } while(next_permutation(s.begin(), s.end()));
 
    }
 return 0;
}