打印字符串的所有子序列-yiteyi-C++库

给定一个字符串，我们必须找出它的所有子序列。字符串是给定字符串的子序列，通过删除给定字符串的某些字符而不改变其顺序来生成。

null

例如：

Input : abcOutput : a, b, c, ab, bc, ac, abcInput : aaaOutput : a, aa, aaa

推荐：请尝试你的方法 {IDE} 首先，在进入解决方案之前。

方法1（选择和不选择概念）

C++

                         // C++ program for the above approach                       
                         #include <bits/stdc++.h>                       
                         using                                     namespace                                     std;                       
           
                         // Find all subsequences                       
                         void                                     printSubsequence(string input, string output)                       
                         {                       
                                                 // Base Case                       
                                                 // if the input is empty print the output string                       
                                                 if                                     (input.empty()) {                       
                                                 cout << output << endl;                       
                                                 return                                     ;                       
                                                 }                       
           
                                                 // output is passed with including                       
                                                 // the Ist character of                       
                                                 // Input string                       
                                                 printSubsequence(input.substr(1), output + input[0]);                       
           
                                                 // output is passed without                       
                                                 // including the Ist character                       
                                                 // of Input string                       
                                                 printSubsequence(input.substr(1), output);                       
                         }                       
           
                         // Driver code                       
                         int                                     main()                       
                         {                       
                                                 // output is set to null before passing in as a                       
                                                 // parameter                       
                                                 string output =                                     ""                                     ;                       
                                                 string input =                                     "abcd"                                     ;                       
           
                                                 printSubsequence(input, output);                       
           
                                                 return                                     0;                       
                         }                       

JAVA

                         // Java program for the above approach                       
                         import                                     java.util.*;                       
                         class                                     GFG {                       
           
                                                 // Declare a global list                       
                                                 static                                     List<String> al =                                     new                                     ArrayList<>();                       
           
                                                 // Creating a public static Arraylist such that                       
                                                 // we can store values                       
                                                 // IF there is any question of returning the                       
                                                 // we can directly return too// public static                       
                                                 // ArrayList<String> al = new ArrayList<String>();                       
                                                 public                                     static                                     void                                     main(String[] args)                       
                                                 {                       
                                                 String s =                                     "abcd"                                     ;                       
                                                 findsubsequences(s,                                     ""                                     );                                     // Calling a function                       
                                                 System.out.println(al);                       
                                                 }                       
           
                                                 private                                     static                                     void                                     findsubsequences(String s,                       
                                                 String ans)                       
                                                 {                       
                                                 if                                     (s.length() ==                                     0                                     ) {                       
                                                 al.add(ans);                       
                                                 return                                     ;                       
                                                 }                       
           
                                                 // We add adding 1st character in string                       
                                                 findsubsequences(s.substring(                                     1                                     ), ans + s.charAt(                                     0                                     ));                       
           
                                                 // Not adding first character of the string                       
                                                 // because the concept of subsequence either                       
                                                 // character will present or not                       
                                                 findsubsequences(s.substring(                                     1                                     ), ans);                       
                                                 }                       
                         }                       

Python3

                         # Below is the implementation of the above approach                       
                         def                                     printSubsequence(                                     input                                     , output):                       
           
                                                 # Base Case                       
                                                 # if the input is empty print the output string                       
                                                 if                                     len                                     (                                     input                                     )                                     =                                     =                                     0                                     :                       
                                                 print                                     (output, end                                     =                                     ' '                                     )                       
                                                 return                       
           
                                                 # output is passed with including the                       
                                                 # 1st character of input string                       
                                                 printSubsequence(                                     input                                     [                                     1                                     :], output                                     +                                     input                                     [                                     0                                     ])                       
           
                                                 # output is passed without including the                       
                                                 # 1st character of input string                       
                                                 printSubsequence(                                     input                                     [                                     1                                     :], output)                       
           
           
                         # Driver code                       
                         # output is set to null before passing in                       
                         # as a parameter                       
                         output                                     =                                     ""                       
                         input                                     =                                     "abcd"                       
           
                         printSubsequence(                                     input                                     , output)                       
           
                         # This code is contributed by Tharun Reddy                       

C#

                         // C# program for the above approach                       
                         using                                     System;                       
                         using                                     System.Collections.Generic;                       
           
                         class                                     GFG{                       
           
                         static                                     void                                     printSubsequence(                                     string                                     input,                       
                                                 string                                     output)                       
                         {                       
                                   
                                                 // Base Case                       
                                                 // If the input is empty print the output string                       
                                                 if                                     (input.Length == 0)                       
                                                 {                       
                                                 Console.WriteLine(output);                       
                                                 return                                     ;                       
                                                 }                       
           
                                                 // Output is passed with including                       
                                                 // the Ist character of                       
                                                 // Input string                       
                                                 printSubsequence(input.Substring(1),                       
                                                 output + input[0]);                       
           
                                                 // Output is passed without                       
                                                 // including the Ist character                       
                                                 // of Input string                       
                                                 printSubsequence(input.Substring(1),                       
                                                 output);                       
                         }                       
           
                         // Driver code                       
                         static                                     void                                     Main()                       
                         {                       
                                   
                                                 // output is set to null before passing                       
                                                 // in as a parameter                       
                                                 string                                     output =                                     ""                                     ;                       
                                                 string                                     input =                                     "abcd"                                     ;                       
                                   
                                                 printSubsequence(input, output);                       
                         }                       
                         }                       
                                   
                         // This code is contributed by SoumikMondal                       

Javascript

                         <script>                       
           
                         // JavaScript program for the above approach                       
           
                         // Find all subsequences                       
                         function                                     printSubsequence(input, output)                       
                         {                       
                                                 // Base Case                       
                                                 // if the input is empty print the output string                       
                                                 if                                     (input.length==0) {                       
                                                 document.write( output +                                     "<br>"                                     );                       
                                                 return                                     ;                       
                                                 }                       
           
                                                 // output is passed with including                       
                                                 // the Ist character of                       
                                                 // Input string                       
                                                 printSubsequence(input.substring(1), output + input[0]);                       
           
                                                 // output is passed without                       
                                                 // including the Ist character                       
                                                 // of Input string                       
                                                 printSubsequence(input.substring(1), output);                       
                         }                       
           
                         // Driver code                       
                         // output is set to null before passing in as a                       
                         // parameter                       
                         var                                     output =                                     ""                                     ;                       
                         var                                     input =                                     "abcd"                                     ;                       
                         printSubsequence(input, output);                       
           
           
                         </script>                       

输出

abcdabcabdabacdacadabcdbcbdbcdcd

方法2 说明：

Step 1: Iterate over the entire StringStep 2: Iterate from the end of string         in order to generate different substring        add the substring to the listStep 3: Drop kth character from the substring obtained         from above to generate different subsequence.Step 4: if the subsequence is not in the list then recur.

以下是该方法的实施情况。

C++

                         // CPP program to print all subsequence of a                       
                         // given string.                       
                         #include <bits/stdc++.h>                       
                         using                                     namespace                                     std;                       
           
                         // set to store all the subsequences                       
                         unordered_set<string> st;                       
           
                         // Function computes all the subsequence of an string                       
                         void                                     subsequence(string str)                       
                         {                       
           
                                                 // Iterate over the entire string                       
                                                 for                                     (                                     int                                     i = 0; i < str.length(); i++) {                       
           
                                                 // Iterate from the end of the string                       
                                                 // to generate substrings                       
                                                 for                                     (                                     int                                     j = str.length(); j > i; j--) {                       
                                                 string sub_str = str.substr(i, j);                       
                                                 st.insert(sub_str);                       
           
                                                 // Drop kth character in the substring                       
                                                 // and if its not in the set then recur                       
                                                 for                                     (                                     int                                     k = 1; k < sub_str.length(); k++) {                       
                                                 string sb = sub_str;                       
           
                                                 // Drop character from the string                       
                                                 sb.erase(sb.begin() + k);                       
                                                 subsequence(sb);                       
                                                 }                       
                                                 }                       
                                                 }                       
                         }                       
           
                         // Driver Code                       
                         int                                     main()                       
                         {                       
                                                 string s =                                     "aabc"                                     ;                       
                                                 subsequence(s);                       
                                                 for                                     (                                     auto                                     i : st)                       
                                                 cout << i <<                                     " "                                     ;                       
                                                 cout << endl;                       
           
                                                 return                                     0;                       
                         }                       
           
                         // This code is contributed by                       
                         // sanjeev2552                       

JAVA

                         // Java Program to print all subsequence of a                       
                         // given string.                       
                         import                                     java.util.HashSet;                       
           
                         public                                     class                                     Subsequence {                       
           
                                                 // Set to store all the subsequences                       
                                                 static                                     HashSet<String> st =                                     new                                     HashSet<>();                       
           
                                                 // Function computes all the subsequence of an string                       
                                                 static                                     void                                     subsequence(String str)                       
                                                 {                       
           
                                                 // Iterate over the entire string                       
                                                 for                                     (                                     int                                     i =                                     0                                     ; i < str.length(); i++) {                       
           
                                                 // Iterate from the end of the string                       
                                                 // to generate substrings                       
                                                 for                                     (                                     int                                     j = str.length(); j > i; j--) {                       
                                                 String sub_str = str.substring(i, j);                       
           
                                                 if                                     (!st.contains(sub_str))                       
                                                 st.add(sub_str);                       
           
                                                 // Drop kth character in the substring                       
                                                 // and if its not in the set then recur                       
                                                 for                                     (                                     int                                     k =                                     1                                     ; k < sub_str.length() -                                     1                                     ;                       
                                                 k++) {                       
                                                 StringBuffer sb                       
                                                 =                                     new                                     StringBuffer(sub_str);                       
           
                                                 // Drop character from the string                       
                                                 sb.deleteCharAt(k);                       
                                                 if                                     (!st.contains(sb))                       
                                                 ;                       
                                                 subsequence(sb.toString());                       
                                                 }                       
                                                 }                       
                                                 }                       
                                                 }                       
           
                                                 // Driver code                       
                                                 public                                     static                                     void                                     main(String[] args)                       
                                                 {                       
                                                 String s =                                     "aabc"                                     ;                       
                                                 subsequence(s);                       
                                                 System.out.println(st);                       
                                                 }                       
                         }                       

输出

aab aa aac bc b abc aabc ab ac a c

方法3： 一个接一个地修复字符，并递归生成从它们开始的所有子集。在每次递归调用之后，我们删除最后一个字符，以便生成下一个置换。

C++

                         // CPP program to generate power set in                       
                         // lexicographic order.                       
                         #include <bits/stdc++.h>                       
                         using                                     namespace                                     std;                       
           
                         // str : Stores input string                       
                         // n : Length of str.                       
                         // curr : Stores current permutation                       
                         // index : Index in current permutation, curr                       
                         void                                     printSubSeqRec(string str,                                     int                                     n,                                     int                                     index = -1,                       
                                                 string curr =                                     ""                                     )                       
                         {                       
                                                 // base case                       
                                                 if                                     (index == n)                       
                                                 return                                     ;                       
           
                                                 if                                     (!curr.empty()) {                       
                                                 cout << curr <<                                     ""                                     ;                       
                                                 }                       
           
                                                 for                                     (                                     int                                     i = index + 1; i < n; i++) {                       
           
                                                 curr += str[i];                       
                                                 printSubSeqRec(str, n, i, curr);                       
           
                                                 // backtracking                       
                                                 curr = curr.erase(curr.size() - 1);                       
                                                 }                       
                                                 return                                     ;                       
                         }                       
           
                         // Generates power set in lexicographic                       
                         // order.                       
                         void                                     printSubSeq(string str)                       
                         {                       
                                                 printSubSeqRec(str, str.size());                       
                         }                       
           
                         // Driver code                       
                         int                                     main()                       
                         {                       
                                                 string str =                                     "cab"                                     ;                       
                                                 printSubSeq(str);                       
                                                 return                                     0;                       
                         }                       

JAVA

                         // Java program to generate power set in                       
                         // lexicographic order.                       
                         class                                     GFG {                       
           
                                                 // str : Stores input string                       
                                                 // n : Length of str.                       
                                                 // curr : Stores current permutation                       
                                                 // index : Index in current permutation, curr                       
                                                 static                                     void                                     printSubSeqRec(String str,                                     int                                     n,                                     int                                     index,                       
                                                 String curr)                       
                                                 {                       
                                                 // base case                       
                                                 if                                     (index == n) {                       
                                                 return                                     ;                       
                                                 }                       
                                                 if                                     (curr !=                                     null                                     && !curr.trim().isEmpty()) {                       
                                                 System.out.println(curr);                       
                                                 }                       
                                                 for                                     (                                     int                                     i = index +                                     1                                     ; i < n; i++) {                       
                                                 curr += str.charAt(i);                       
                                                 printSubSeqRec(str, n, i, curr);                       
           
                                                 // backtracking                       
                                                 curr = curr.substring(                                     0                                     , curr.length() -                                     1                                     );                       
                                                 }                       
                                                 }                       
           
                                                 // Generates power set in                       
                                                 // lexicographic order.                       
                                                 static                                     void                                     printSubSeq(String str)                       
                                                 {                       
                                                 int                                     index = -                                     1                                     ;                       
                                                 String curr =                                     ""                                     ;                       
           
                                                 printSubSeqRec(str, str.length(), index, curr);                       
                                                 }                       
           
                                                 // Driver code                       
                                                 public                                     static                                     void                                     main(String[] args)                       
                                                 {                       
                                                 String str =                                     "cab"                                     ;                       
                                                 printSubSeq(str);                       
                                                 }                       
                         }                       
           
                         // This code is contributed by PrinciRaj1992                       

Python3

                         # Python program to generate power set in lexicographic order.                       
           
                                                 # str: Stores input string                       
                                                 # n: Length of str.                       
                                                 # curr: Stores current permutation                       
                                                 # index: Index in current permutation, curr                       
                         def                                     printSubSeqRec(                                     str                                     , n, index                                     =                                     -                                     1                                     , curr                                     =                                     ""):                       
                                                 # base case                       
                                                 if                                     (index                                     =                                     =                                     n):                       
                                                 return                       
                                                 if                                     (                                     len                                     (curr) >                                     0                                     ):                       
                                                 print                                     (curr)                       
           
                                                 i                                     =                                     index                                     +                                     1                       
           
                                                 while                                     (i < n):                       
                                                 curr                                     =                                     curr                                     +                                     str                                     [i]                       
                                                 printSubSeqRec(                                     str                                     , n, i, curr)                       
                                                 curr                                     =                                     curr[                                     0                                     :                                     -                                     1                                     ]                       
                                                 i                                     =                                     i                                     +                                     1                       
                                   
                         #  Generates power set in lexicographic order.                       
                         #  function                       
                         def                                     printSubSeq(                                     str                                     ):                       
                                                 printSubSeqRec(                                     str                                     ,                                     len                                     (                                     str                                     ))                       
           
                         # // Driver code                       
                         str                                     =                                     "cab"                       
                         printSubSeq(                                     str                                     )                       
           
                         # This code is contributed by shinjanpatra                       

Javascript

                         <script>                       
                         // JavaScrpt program to generate power set in                       
                         // lexicographic order.                       
                                   
                         // str : Stores input string                       
                         // n : Length of str.                       
                         // curr : Stores current permutation                       
                         // index : Index in current permutation, curr                       
           
                         function                                     printSubSeqRec(str,n,index = -1,curr =                                     ""                                     )                       
                         {                       
                                                 // base case                       
                                                 if                                     (index == n)                       
                                                 return                                     ;                       
                                   
                                                 if                                     (curr.length>0) {                       
                                                 document.write(curr)                       
                                                 }                       
                                   
                                                 for                                     (let i = index + 1; i < n; i++) {                       
                                   
                                                 curr += str[i];                       
                                                 printSubSeqRec(str, n, i, curr);                       
                                   
                                                 // backtracking                       
                                                 curr = curr.slice(0, - 1);                       
                                                 }                       
                                                 return                                     ;                       
                         }                       
                                   
                         // Generates power set in lexicographic                       
                         // order.                       
                         function                                     printSubSeq(str)                       
                         {                       
                                                 printSubSeqRec(str, str.length);                       
                         }                       
                                   
                         // Driver code                       
           
                         let str =                                     "cab"                                     ;                       
                         printSubSeq(str);                       
                         </script>                       

输出

ccacabcbaabb

本文由 苏米特·戈什 .如果你喜欢GeekSforgek，并想贡献自己的力量，你也可以使用写极客。组织或者把你的文章寄去评论-team@geeksforgeeks.org.看到你的文章出现在Geeksforgeks主页上，并帮助其他极客。如果您发现任何不正确的地方，或者您想分享有关上述主题的更多信息，请写下评论。

文章版权归作者所有，未经允许请勿转载。

THE END

技术文章