Approach 2
- Iterate over all of the Strings.
- Iterate from the end to generate various substrings to the list, add the substring
- To construct a separate subsequence, remove the kth character from the substring acquired above.
- Recur if the subsequence isn't in the list.
C++ implementation
/* C++ program to print all subsequences of a string */
#include <bits/stdc++.h>
using namespace std;
/* set to store and print all subsequences */
unordered_set<string> st;
/* Function computes all the subsequence of a string */
void subsequence(string str)
{
/* Iterate over the entire string */
int i;
for (i = 0; i < str.length(); i++) {
/* Iterate from the end of the string */
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 it’s 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);
}
}
}
}
/* Main Code */
int main()
{
string s = "abcd";
subsequence(s);
for (auto i : st)
cout << i << " ";
cout << endl;
return 0;
}
You can also try this code with Online C++ Compiler
Output
bcd bc abcd acd ab a abd ad d ac cd c b bd abc
Java implementation
/* Java Program to print all subsequences of a string */
import java.util.HashSet;
public class Main {
/* Set to store and print all 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 */
int i;
for (i = 0; i < str.length(); i++) {
/* Iterate from the end of the string */
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 it’s 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());
}
}
}
}
/* Main code */
public static void main(String[] args)
{
String s = "abcd";
subsequence(s);
System.out.println(st);
}
}
You can also try this code with Online Java Compiler
Output
[a, cd, ab, bc, ac, abd, bd, b, bcd, acd, ad, c, abc, d, abcd]
Complexities
Time complexity
O(n5log n), where n is the length of the string
Reason: Total n2 recursive functions to be called, and each function has O(n3) time complexity and insert function in unordered map takes log n. Thus, the total time complexity for this program will be O(n5)
Space complexity
O(n2), where n is the length of the string
Reason: Total n2 recursive functions to be called, and stored in an ordered map.
Read More - Time Complexity of Sorting Algorithms
Also check out - Substr C++
Approach 3
Fix characters one by one and recursively produce all subgroups from there. We eliminate the last character after each recursive call so that the next permutation can be formed. Thus, we print all subsequences of a given string.
- Iterate over the string.
- Now, use for loop to add all characters to output once and call the same function while resetting output to the previous value.
- Print the output if it is not an empty string.
C++ implementation
/* C++ program to print all subsequences of a string */
#include <bits/stdc++.h>
using namespace std;
/* str: Stores input string
n : length of string str.
curr : Stores current permutation
index : Index in current permutation, curr */
void printSubSeqRec(string str, int n, int index = -1,
string curr = "")
{
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());
}
/* Main code */
int main()
{
string str = "abcd";
printSubSeq(str);
return 0;
}
You can also try this code with Online C++ Compiler
Output
a
ab
abc
abcd
abd
ac
acd
ad
b
bc
bcd
bd
c
cd
d
Java implementation
/* Java program to print all subsequences of a string */
class Main {
/* str: Stores input string
n : length of string str.
curr : Stores current permutation
index : Index in current permutation, curr */
static void printSubSequenceRec(String str, int n, int index,
String curr)
{
if (index == n) {
return;
}
if (curr != null && !curr.trim().isEmpty()) {
System.out.println(curr);
}
int i;
for (i = index + 1; i < n; i++) {
curr += str.charAt(i);
printSubSequenceRec(str, n, i, curr);
curr = curr.substring(0, curr.length() - 1);
}
}
/* Generates power set in lexicographic order. */
static void printSubSequence(String str)
{
int index = -1;
String curr = "";
printSubSequenceRec(str, str.length(), index, curr);
}
/* Main code */
public static void main(String[] args)
{
String str = "abcd";
printSubSequence(str);
}
}
You can also try this code with Online Java Compiler
Output
a
ab
abc
abcd
abd
ac
acd
ad
b
bc
bcd
bd
c
cd
d
Complexities
Time complexity
O(nn), where n is the length of the string
Reason: Total nn recursive functions to be called, and each function has O(1) time complexity. Thus, the total time complexity for this program will be O(nn)
Space complexity
O(1)
Reason: No extra variable space is needed.
FAQs
-
What is a subsequence?
A subsequence is a sequence created by eliminating some characters from a string while keeping the order of the remaining characters the same.
-
Difference between subsequence and substring?
A substring is the contiguous part of the string. If a string is n characters long, the number of substrings equals n*(n+1)/2.
-
What is a string in C++?
A string is the sequence of characters in C++. C++ offers a string class with which you can store your string in an object.
-
Is it possible to create a string object in C?
No, you can only store your string as a character in an array in C. The C language lacks a string class, but C++ does.
-
Does the strlen() function take into account null characters when calculating length?
No, strlen() does not include null characters in the string length. It merely counts the length of the string's characters.
Key Takeaways
In this article, we have tried to print all possible sequences of a string. We hope that this question will help you understand the concept of string problems, and if you would like to learn more about it, check out our other problems on subsequences of a string & Print All Subsequences Of A String.
Recommended Reads, Permutation of string
Attempt our Online Mock Test Series on Coding Ninjas Studio now!
Happy Coding!
568+ registered 
