给定一个整数K。任务是打印大小为K（给定数字）的所有二进制字符串。 例如：
null
Input : K = 3 Output : 000 , 001 , 010 , 100 , 101 Input : K = 4 Output :0000 0001 0010 0100 0101 1000 1001 1010
其背后的想法是，如果字符串以“1”结尾，那么我们只在末尾放“0”。如果字符串以“0”结尾，那么我们将“0”和“1”放在字符串的末尾，以生成新字符串。 下面是算法
K : size of string First We Generate All string starts with '0'initialize n = 1 . GenerateALLString ( K , Str , n ) a. IF n == K PRINT str. b. IF previous character is '1' :: str[n-1] == '1' put str[n] = '0' GenerateAllString ( K , str , n+1 ) c. IF previous character is '0' :: str[n-1] == '0' First We Put zero at end and call function PUT str[n] = '0' GenerateAllString ( K , str , n+1 ) PUT str[n] = '1' GenerateAllString ( K , str , n+1 )Second Generate all binary string starts with '1'DO THE SAME PROCESS
下面是递归实现：
C++
// C++ program to Generate // all binary string without // consecutive 1's of size K #include<bits/stdc++.h> using namespace std ; // A utility function generate all string without // consecutive 1'sof size K void generateAllStringsUtil( int K, char str[], int n) { // Print binary string without consecutive 1's if (n == K) { // Terminate binary string str[n] = ' ' ; cout << str << " " ; return ; } // If previous character is '1' then we put // only 0 at end of string //example str = "01" then new string be "010" if (str[n-1] == '1' ) { str[n] = '0' ; generateAllStringsUtil (K , str , n+1); } // If previous character is '0' than we put // both '1' and '0' at end of string // example str = "00" then // new string "001" and "000" if (str[n-1] == '0' ) { str[n] = '0' ; generateAllStringsUtil(K, str, n+1); str[n] = '1' ; generateAllStringsUtil(K, str, n+1) ; } } // Function generate all binary string without // consecutive 1's void generateAllStrings( int K ) { // Base case if (K <= 0) return ; // One by one stores every // binary string of length K char str[K]; // Generate all Binary string // starts with '0' str[0] = '0' ; generateAllStringsUtil ( K , str , 1 ) ; // Generate all Binary string // starts with '1' str[0] = '1' ; generateAllStringsUtil ( K , str , 1 ); } // Driver program to test above function int main() { int K = 3; generateAllStrings (K) ; return 0; } |
JAVA
// Java program to Generate all binary string without // consecutive 1's of size K import java.util.*; import java.lang.*; public class BinaryS { // Array conversion to String-- public static String toString( char [] a) { String string = new String(a); return string; } static void generate( int k, char [] ch, int n) { // Base Condition when we // reached at the end of Array** if (n == k) { // Printing the Generated String** // Return to the previous case* System.out.print(toString(ch)+ " " ); return ; } // If the first Character is //Zero then adding** if (ch[n - 1 ] == '0' ) { ch[n] = '0' ; generate(k, ch, n + 1 ); ch[n] = '1' ; generate(k, ch, n + 1 ); } // If the Character is One // then add Zero to next** if (ch[n - 1 ] == '1' ) { ch[n] = '0' ; // Calling Recursively for the // next value of Array generate(k, ch, n + 1 ); } } static void fun( int k) { if (k <= 0 ) { return ; } char [] ch = new char [k]; // Initializing first character to Zero ch[ 0 ] = '0' ; // Generating Strings starting with Zero-- generate(k, ch, 1 ); // Initialized first Character to one-- ch[ 0 ] = '1' ; generate(k, ch, 1 ); } public static void main(String args[]) { int k = 3 ; //Calling function fun with argument k fun(k); //This code is Contributed by Praveen Tiwari } } |
Python3
# Python3 program to Generate all binary string # without consecutive 1's of size K # A utility function generate all string without # consecutive 1'sof size K def generateAllStringsUtil(K, str , n): # print binary string without consecutive 1's if (n = = K): # terminate binary string print ( * str [:n], sep = " ", end = " ") return # if previous character is '1' then we put # only 0 at end of string # example str = "01" then new string be "000" if ( str [n - 1 ] = = '1' ): str [n] = '0' generateAllStringsUtil (K, str , n + 1 ) # if previous character is '0' than we put # both '1' and '0' at end of string # example str = "00" then new string "001" and "000" if ( str [n - 1 ] = = '0' ): str [n] = '0' generateAllStringsUtil(K, str , n + 1 ) str [n] = '1' generateAllStringsUtil(K, str , n + 1 ) # function generate all binary string without # consecutive 1's def generateAllStrings(K): # Base case if (K < = 0 ): return # One by one stores every # binary string of length K str = [ 0 ] * K # Generate all Binary string starts with '0' str [ 0 ] = '0' generateAllStringsUtil (K, str , 1 ) # Generate all Binary string starts with '1' str [ 0 ] = '1' generateAllStringsUtil (K, str , 1 ) # Driver code K = 3 generateAllStrings (K) # This code is contributed by SHUBHAMSINGH10 |
C#
// C# program to Generate // all binary string without // consecutive 1's of size K using System; class GFG { // Array conversion to String-- static string toString( char [] a) { string String = new string (a); return String; } static void generate( int k, char [] ch, int n) { // Base Condition when we // reached at the end of Array** if (n == k) { // Printing the Generated String** // Return to the previous case* Console.Write(toString(ch)+ " " ); return ; } // If the first Character is //Zero then adding** if (ch[n - 1] == '0' ) { ch[n] = '0' ; generate(k, ch, n + 1); ch[n] = '1' ; generate(k, ch, n + 1); } // If the Character is One // then add Zero to next** if (ch[n - 1] == '1' ) { ch[n] = '0' ; // Calling Recursively for the // next value of Array generate(k, ch, n + 1); } } static void fun( int k) { if (k <= 0) { return ; } char [] ch = new char [k]; // Initializing first character to Zero ch[0] = '0' ; // Generating Strings starting with Zero-- generate(k, ch, 1); // Initialized first Character to one-- ch[0] = '1' ; generate(k, ch, 1); } // Driver code static void Main() { int k = 3; //Calling function fun with argument k fun(k); } } // This code is contributed by divyeshrabadiya07. |
Javascript
<script> // Javascript implementation // A utility function generate all string without // consecutive 1'sof size K function generateAllStringsUtil(K, str, n) { // Print binary string without consecutive 1's if (n == K) { // Terminate binary string str[n] = ' ' ; document.write(str.join( "" ) + " " ); return ; } // If previous character is '1' then we put // only 0 at end of string //example str = "01" then new string be "010" if (str[n-1] == '1' ) { str[n] = '0' ; generateAllStringsUtil (K , str , n+1); } // If previous character is '0' than we put // both '1' and '0' at end of string // example str = "00" then // new string "001" and "000" if (str[n-1] == '0' ) { str[n] = '0' ; generateAllStringsUtil(K, str, n+1); str[n] = '1' ; generateAllStringsUtil(K, str, n+1) ; } } // Function generate all binary string without // consecutive 1's function generateAllStrings(K ) { // Base case if (K <= 0) return ; // One by one stores every // binary string of length K var str = new Array(K); // Generate all Binary string // starts with '0' str[0] = '0 ' ; generateAllStringsUtil ( K , str , 1 ) ; // Generate all Binary string // starts with ' 1 ' str[0] = ' 1' ; generateAllStringsUtil ( K , str , 1 ); } /* Driver code */ var K = 3; generateAllStrings(K); // This is code is contributed // by shivani </script> |
输出：
000 001 010 100 101
这个问题是通过使用递归树来解决的，递归树有两种可能性0或1，就像在子序列中选择元素一样。
因此，我们也可以使用布尔数组实现上述方法。
C++14
#include <bits/stdc++.h> using namespace std; void All_Binary_Strings( bool arr[], int num, int r) { if (r==num) { for ( int i=0;i<num;i++) cout<<arr[i]; cout<< " " ; return ; } else if (arr[r-1]) { arr[r]=0; All_Binary_Strings(arr,num,r+1); } else { arr[r]=0; All_Binary_Strings(arr,num,r+1); arr[r]=1; All_Binary_Strings(arr,num,r+1); } } void print( bool a[], int & num) { a[0]=0; All_Binary_Strings(a,num,1); a[0]=1; All_Binary_Strings(a,num,1); } //driver's code int main() { int n=2; bool a[n]; print(a,n); return 0; } |
上述方法也可以使用字符串解决。它对复杂性没有任何影响，但字符串处理、打印和操作都很简单。
C++14
#include <bits/stdc++.h> using namespace std; void All_Binary_Strings(string str, int num) { int len=str.length(); if (len==num) { cout<<str<< " " ; return ; } else if (str[len-1]== '1' ) All_Binary_Strings(str+ '0' ,num); else { All_Binary_Strings(str+ '0' ,num); All_Binary_Strings(str+ '1' ,num); } } void print( int & num) { string word; word.push_back( '0' ); All_Binary_Strings(word,num); word[0]= '1' ; All_Binary_Strings(word,num); } //driver's code int main() { int n=4; print(n); return 0; } |
Javascript
<script> function All_Binary_Strings(str,num) { let len = str.length; if (len == num) { document.write(str, " " ); return ; } else if (str[len - 1]== '1' ) All_Binary_Strings(str+ '0' ,num); else { All_Binary_Strings(str+ '0' ,num); All_Binary_Strings(str+ '1' ,num); } } function print(num) { let word = "" ; word += '0' ; All_Binary_Strings(word,num); word = '1' ; All_Binary_Strings(word,num); } // driver's code let n = 4; print(n); // This code is contributed by shinjanpatra. </script> |
时间复杂性： O（2^n）
辅助空间： O（n）
本文由 尼桑·辛格 .如果你喜欢GeekSforgek，并想贡献自己的力量，你也可以使用 写极客。组织 或者把你的文章寄去评论-team@geeksforgeeks.org.看到你的文章出现在Geeksforgeks主页上，并帮助其他极客。 如果您发现任何不正确的地方，或者您想分享有关上述主题的更多信息，请写下评论。
© 版权声明
文章版权归作者所有，未经允许请勿转载。
THE END
![关于”PostgreSQL错误：关系[表]不存在“问题的原因和解决方案-yiteyi-C++库](https://www.yiteyi.com/wp-content/themes/zibll/img/thumbnail.svg)
