# 算法：如何实现打印字符串的所有子序列？|迭代法

2021年3月19日18:22:25 发表评论 381 次浏览

## 本文概述

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

Input : aab
Output : a, b, aa, ab, aab``````

## 推荐：请尝试以下方法{IDE}首先, 在继续解决方案之前。

input =" abc"

001 => abc。只有c对应于比特1。因此, 子序列= c。

101 => abc。 a和c对应于比特1。因此, 子序列= ac。

binary_representation(1)= 001 => c

binary_representation(2)= 010 => b

binary_representation(3)= 011 => bc

binary_representation(4)= 100 =>一个

binary_representation(5)= 101 =>交流

binary_representation(7)= 111 => abc

## C ++

``````// CPP program to print all Subsequences
// of a string in iterative manner
#include <bits/stdc++.h>
using namespace std;

// function to find subsequence
string subsequence(string s, int binary, int len)
{
string sub = "" ;
for ( int j = 0; j < len; j++)

// check if jth bit in binary is 1
if (binary & (1 << j))

// if jth bit is 1, include it
// in subsequence
sub += s[j];

return sub;
}

// function to print all subsequences
void possibleSubsequences(string s){

// map to store subsequence
// lexicographically by length
map< int , set<string> > sorted_subsequence;

int len = s.size();

// Total number of non-empty subsequence
// in string is 2^len-1
int limit = pow (2, len);

// i=0, corresponds to empty subsequence
for ( int i = 1; i <= limit - 1; i++) {

// subsequence for binary pattern i
string sub = subsequence(s, i, len);

// storing sub in map
sorted_subsequence[sub.length()].insert(sub);
}

for ( auto it : sorted_subsequence) {

// it.first is length of Subsequence
// it.second is set<string>
cout << "Subsequences of length = "
<< it.first << " are:" << endl;

for ( auto ii : it.second)

// ii is iterator of type set<string>
cout << ii << " " ;

cout << endl;
}
}

// driver function
int main()
{
string s = "aabc" ;
possibleSubsequences(s);
return 0;
}``````

## Python3

``````# Python3 program to print all Subsequences
# of a string in iterative manner

# function to find subsequence
def subsequence(s, binary, length):
sub = ""
for j in range (length):

# check if jth bit in binary is 1
if (binary & ( 1 << j)):

# if jth bit is 1, include it
# in subsequence
sub + = s[j]
return sub

# function to print all subsequences
def possibleSubsequences(s):

# map to store subsequence
# lexicographically by length
sorted_subsequence = {}

length = len (s)

# Total number of non-empty subsequence
# in string is 2^len-1
limit = 2 * * length

# i=0, corresponds to empty subsequence
for i in range ( 1 , limit):

# subsequence for binary pattern i
sub = subsequence(s, i, length)

# storing sub in map
if len (sub) in sorted_subsequence.keys():
sorted_subsequence[ len (sub)] = \
tuple ( list (sorted_subsequence[ len (sub)]) + [sub])
else :
sorted_subsequence[ len (sub)] = [sub]

for it in sorted_subsequence:

# it.first is length of Subsequence
# it.second is set<string>
print ( "Subsequences of length =" , it, "are:" )
for ii in sorted ( set (sorted_subsequence[it])):

# ii is iterator of type set<string>
print (ii, end = ' ' )
print ()

# Driver Code
s = "aabc"
possibleSubsequences(s)

# This code is contributed by ankush_953``````

``````Subsequences of length = 1 are:
a b c
Subsequences of length = 2 are:
aa ab ac bc
Subsequences of length = 3 are:
aab aac abc
Subsequences of length = 4 are:
aabc``````

, 其中n是查找子序列的字符串的长度, l是二进制字符串的长度。

001 => abc。只有c对应于比特1。因此, 子序列= c

101 => abc。 a和c对应于比特1。因此, 子序列= ac。

binary_representation(1)= 001 => c

binary_representation(2)= 010 => b

binary_representation(3)= 011 => bc

binary_representation(4)= 100 =>一个

binary_representation(5)= 101 =>交流

binary_representation(7)= 111 => abc

## C ++

``````// CPP code all Subsequences of a
// string in iterative manner
#include <bits/stdc++.h>
using namespace std;

// function to find subsequence
string subsequence(string s, int binary)
{
string sub = "" ;
int pos;

// loop while binary is greater than 0
while (binary>0)
{
// get the position of rightmost set bit
pos=log2(binary&-binary)+1;

// append at beginning as we are
// going from LSB to MSB
sub=s[pos-1]+sub;

// resets bit at pos in binary
binary= (binary & ~(1 << (pos-1)));
}
reverse(sub.begin(), sub.end());
return sub;
}

// function to print all subsequences
void possibleSubsequences(string s){

// map to store subsequence
// lexicographically by length
map< int , set<string> > sorted_subsequence;

int len = s.size();

// Total number of non-empty subsequence
// in string is 2^len-1
int limit = pow (2, len);

// i=0, corresponds to empty subsequence
for ( int i = 1; i <= limit - 1; i++) {

// subsequence for binary pattern i
string sub = subsequence(s, i);

// storing sub in map
sorted_subsequence[sub.length()].insert(sub);
}

for ( auto it : sorted_subsequence) {

// it.first is length of Subsequence
// it.second is set<string>
cout << "Subsequences of length = "
<< it.first << " are:" << endl;

for ( auto ii : it.second)

// ii is iterator of type set<string>
cout << ii << " " ;

cout << endl;
}
}

// driver function
int main()
{
string s = "aabc" ;
possibleSubsequences(s);

return 0;
}``````

## Python3

``````# Python3 program to print all Subsequences
# of a string in an iterative manner
from math import log2, floor

# function to find subsequence
def subsequence(s, binary):
sub = ""

# loop while binary is greater than
while (binary > 0 ):

# get the position of rightmost set bit
pos = floor(log2(binary& - binary) + 1 )

# append at beginning as we are
# going from LSB to MSB
sub = s[pos - 1 ] + sub

# resets bit at pos in binary
binary = (binary & ~( 1 << (pos - 1 )))

sub = sub[:: - 1 ]
return sub

# function to print all subsequences
def possibleSubsequences(s):

# map to store subsequence
# lexicographically by length
sorted_subsequence = {}

length = len (s)

# Total number of non-empty subsequence
# in string is 2^len-1
limit = 2 * * length

# i=0, corresponds to empty subsequence
for i in range ( 1 , limit):

# subsequence for binary pattern i
sub = subsequence(s, i)

# storing sub in map
if len (sub) in sorted_subsequence.keys():
sorted_subsequence[ len (sub)] = \
tuple ( list (sorted_subsequence[ len (sub)]) + [sub])
else :
sorted_subsequence[ len (sub)] = [sub]

for it in sorted_subsequence:

# it.first is length of Subsequence
# it.second is set<string>
print ( "Subsequences of length =" , it, "are:" )
for ii in sorted ( set (sorted_subsequence[it])):

# ii is iterator of type set<string>
print (ii, end = ' ' )
print ()

# Driver Code
s = "aabc"
possibleSubsequences(s)

# This code is contributed by ankush_953``````

``````Subsequences of length = 1 are:
a b c
Subsequences of length = 2 are:
aa ab ac bc
Subsequences of length = 3 are:
aab aac abc
Subsequences of length = 4 are:
aabc``````

, 其中n是找到子序列的字符串的长度, b是二进制字符串中设置的位数。