算法（如何打印字符串的所有子序列（）） _字符串所有子序列

本文概述

Java
C ++
Java
C ++
Java

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

Input : abc Output : a, b, c, ab, bc, ac, abcInput : 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

【算法（如何打印字符串的所有子序列（））】输出如下：