算法：如何打印字符串的所有子序列？

本文概述

• Java
• C ++
• Java
• C ++
• Java

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

例子：

Input : abc
Output : a, b, c, ab, bc, ac, abc

Input : aaa
Output : a, aa, aaa

推荐：请尝试以下方法

{IDE}

首先, 在继续解决方案之前。

方法1(选择和不选择概念)  

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

输出如下：

[abcd, abc, abd, ab, acd, ac, ad, a, bcd, bc, bd, b, cd, c, d, ]

方法2

说明：

Step 1: Iterate over the entire String
Step 2: Iterate from the end of string 
        in order to generate different substring
        add the subtring to the list
Step 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 rogram 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() - 1; 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);
     }
}

输出如下：

[aa, a, ab, bc, ac, b, aac, abc, c, aab, aabc]

方法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 << "\n" ;
     }
 
     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

输出如下： 

c
ca
cab
cb
a
ab
b