# UAV 729 The Hamming Distance Backtracking Problem

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; }

## Leave a Reply