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.
|
1 2 3 4 5 6 7 8 9 10 |
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:
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 |
#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