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

2021年3月19日12:59:16 发表评论 398 次浏览

## 本文概述

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

Input : aaa
Output : a, aa, aaa``````

{IDE}

## 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
// 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 ) {
return ;
}

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, ]``

``````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))

// 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]``

## 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``````