Print all subsequences of a string using ArrayList
Last Updated : 01 Nov, 2023
Given a string str, the task is to print all the sub-sequences of str.
A subsequence is a sequence that can be derived from another sequence by deleting some or no elements without changing the order of the remaining elements.
Examples:
Input: str = "abc"
Output: a b ab c ac bc abc
Input: str = "geek"
Output: g e ge e ge ee gee k gk ek gek ek gek eek geek
Approach: Write a recursive function that prints every sub-sequence of the sub-string starting from the second character str[1, n - 1] after appending the first character of the string str[0] in the beginning of every sub-sequence. Terminating condition will be when the passed string is empty, in that case the function will return an empty arraylist.
Below is the implementation of the above approach:
C++ // C++ implementation of the approach #include <bits/stdc++.h> using namespace std; // Utility function to print the contents // of the List void printList(vector<string> arrL) { arrL.erase(find(arrL.begin(), arrL.end(), "")); for (int i = 0; i < arrL.size(); i++) cout << arrL[i] << " "; } // Function to returns the arraylist which contains // all the sub-sequences of str vector<string> getSequence(string str) { // If string is empty if (str.length() == 0) { // Return an empty arraylist vector<string> empty; empty.push_back(""); return empty; } // Take first character of str char ch = str[0]; // Take sub-string starting from the // second character string subStr = str.substr(1); // Recursive call for all the sub-sequences // starting from the second character vector<string> subSequences = getSequence(subStr); // Add first character from str in the beginning // of every character from the sub-sequences // and then store it into the resultant arraylist vector<string> res; for(string val : subSequences) { res.push_back(val); res.push_back(ch + val); } // Return the resultant arraylist return res; } int main() { string str = "geek"; printList(getSequence(str)); return 0; } // This code is contributed by rameshtravel07. // Java implementation of the approach import java.util.ArrayList; public class GFG { // Utility function to print the contents // of the ArrayList static void printArrayList(ArrayList<String> arrL) { arrL.remove(""); for (int i = 0; i < arrL.size(); i++) System.out.print(arrL.get(i) + " "); } // Function to returns the arraylist which contains // all the sub-sequences of str public static ArrayList<String> getSequence(String str) { // If string is empty if (str.length() == 0) { // Return an empty arraylist ArrayList<String> empty = new ArrayList<>(); empty.add(""); return empty; } // Take first character of str char ch = str.charAt(0); // Take sub-string starting from the // second character String subStr = str.substring(1); // Recursive call for all the sub-sequences // starting from the second character ArrayList<String> subSequences = getSequence(subStr); // Add first character from str in the beginning // of every character from the sub-sequences // and then store it into the resultant arraylist ArrayList<String> res = new ArrayList<>(); for (String val : subSequences) { res.add(val); res.add(ch + val); } // Return the resultant arraylist return res; } // Driver code public static void main(String[] args) { String str = "geek"; printArrayList(getSequence(str)); // System.out.print(getSequence(str)); } } # Python implementation of the approach # Utility function to print the contents # of the ArrayList def printArrayList(arrL): arrL.remove("") print(*arrL, sep = " ") # Function to returns the arraylist which contains # all the sub-sequences of str def getSequence(Str): # If string is empty if(len(Str) == 0): # Return an empty arraylist empty = [] empty.append("") return empty # Take first character of str ch = Str[0] # Take sub-string starting from the # second character subStr = Str[1:] # Recursive call for all the sub-sequences # starting from the second character subSequences = getSequence(subStr) # Add first character from str in the beginning # of every character from the sub-sequences # and then store it into the resultant arraylist res = [] for val in subSequences: res.append(val) res.append(ch + val) # Return the resultant arraylist return res # Driver code Str = "geek" printArrayList(getSequence(Str)) # This code is contributed by avanitrachhadiya2155 // C# implementation of the approach using System; using System.Collections.Generic; class GFG{ // Utility function to print the contents // of the List static void printList(List<String> arrL) { arrL.Remove(""); for (int i = 0; i < arrL.Count; i++) Console.Write(arrL[i] + " "); } // Function to returns the arraylist which contains // all the sub-sequences of str public static List<String> getSequence(String str) { // If string is empty if (str.Length == 0) { // Return an empty arraylist List<String> empty = new List<String>(); empty.Add(""); return empty; } // Take first character of str char ch = str[0]; // Take sub-string starting from the // second character String subStr = str.Substring(1); // Recursive call for all the sub-sequences // starting from the second character List<String> subSequences = getSequence(subStr); // Add first character from str in the beginning // of every character from the sub-sequences // and then store it into the resultant arraylist List<String> res = new List<String>(); foreach (String val in subSequences) { res.Add(val); res.Add(ch + val); } // Return the resultant arraylist return res; } // Driver code public static void Main(String[] args) { String str = "geek"; printList(getSequence(str)); // Console.Write(getSequence(str)); } } // This code is contributed by Rohit_ranjan <script> // JavaScript implementation of the approach // Utility function to print the contents // of the ArrayList function printArrayList(arrL) { arrL.splice(arrL.indexOf(""), 1); for (let i = 0; i < arrL.length; i++) document.write(arrL[i] + " "); } // Function to returns the arraylist which contains // all the sub-sequences of str function getSequence(str) { // If string is empty if (str.length == 0) { // Return an empty arraylist let empty = []; empty.push(""); return empty; } // Take first character of str let ch = str[0]; // Take sub-string starting from the // second character let subStr = str.substring(1); // Recursive call for all the sub-sequences // starting from the second character let subSequences = getSequence(subStr); // Add first character from str in the beginning // of every character from the sub-sequences // and then store it into the resultant arraylist let res = []; for (let val = 0; val < subSequences.length; val++) { res.push(subSequences[val]); res.push(ch + subSequences[val]); } // Return the resultant arraylist return res; } let str = "geek"; printArrayList(getSequence(str)); </script> Outputg e ge e ge ee gee k gk ek gek ek gek eek geek
Time Complexity: O(2^n), where n is the length of the string.
Space Complexity: O(2^n), as the recursive stack grows until the length of the string.
Alternate Solution: One by one fix characters and recursively generate all subsets starting from them.
C++ // C++ implementation of the approach #include <bits/stdc++.h> using namespace std; // Function to print all the sub-sequences // of a string void printSubSeq(string sub, string ans) { if (sub.length() == 0) { cout << "" << ans << " "; return; } // First character of sub char ch = sub[0]; // Sub-string starting from second // character of sub string ros = sub.substr(1); // Excluding first character printSubSeq(ros, ans); // Including first character printSubSeq(ros, ans + ch); } // Driver code int main() { string str = "abc"; printSubSeq(str, ""); return 0; } // This code is contributed by divyesh072019 // Java implementation of the approach public class sub_sequence { // Function to print all the sub-sequences // of a string public static void printSubSeq(String sub, String ans) { if (sub.length() == 0) { System.out.print("" + ans + " "); return; } // First character of sub char ch = sub.charAt(0); // Sub-string starting from second // character of sub String ros = sub.substring(1); // Excluding first character printSubSeq(ros, ans); // Including first character printSubSeq(ros, ans + ch); } // Driver code public static void main(String[] args) { String str = "abc"; printSubSeq(str, ""); } } # Python3 implementation of the approach # Function to print all the sub-sequences # of a string def printSubSeq(sub, ans) : if (len(sub) == 0) : print(ans , end = " ") return # First character of sub ch = sub[0] # Sub-string starting from second # character of sub ros = sub[1 : ] # Excluding first character printSubSeq(ros, ans) # Including first character printSubSeq(ros, ans + ch) Str = "abc" printSubSeq(Str, "") # This code iscontributed by divyeshrabadiya07
// C# implementation of the approach using System; class GFG { // Function to print all the // sub-sequences of a string public static void printSubSeq(string sub, string ans) { if (sub.Length == 0) { Console.Write("" + ans + " "); return; } // First character of sub char ch = sub[0]; // Sub-string starting from second // character of sub string ros = sub.Substring(1); // Excluding first character printSubSeq(ros, ans); // Including first character printSubSeq(ros, ans + ch); } // Driver code public static void Main() { string str = "abc"; printSubSeq(str, "") ; } } // This code is contributed by Ryuga <script> // Javascript implementation of the approach // Function to print all the // sub-sequences of a string function printSubSeq(sub, ans) { if (sub.length == 0) { document.write("" + ans + " "); return; } // First character of sub let ch = sub[0]; // Sub-string starting from second // character of sub let ros = sub.substring(1); // Excluding first character printSubSeq(ros, ans); // Including first character printSubSeq(ros, ans + ch); } let str = "abc"; printSubSeq(str, "") ; // This code is contributed by decode2207. </script> Similar Reads
Print all subsequences of a string Given a string, we have to find out all its subsequences of it. A String is said to be a subsequence of another String, if it can be obtained by deleting 0 or more character without changing its order.Examples: Input : abOutput : "", "a", "b", "ab"Input : abcOutput : "", "a", "b", "c", "ab", "ac", "
12 min read
Print all subsequences of a string | Iterative Method Given a string s, print all possible subsequences of the given string in an iterative manner. We have already discussed Recursive method to print all subsequences of a string. Examples: Input : abc Output : a, b, c, ab, ac, bc, abc Input : aab Output : a, b, aa, ab, aab Approach 1 : Here, we discuss
15 min read
Print all subsequences of a string in Python Given a string s of size n (1 ≤ n ≤ 20), the task is to print all subsequences of string. A subsequence is a sequence that can be derived from another sequence by deleting some or no elements without changing the order of the remaining elements.Examples: Input: s = "abc"Output: ["", "a", "b", "c", "
3 min read
Number of subsequences as "ab" in a string repeated K times Given a String S, consider a new string formed by repeating the S exactly K times. We need find the number of subsequences as “ab†in the newly formed string. Examples : Input : S = "abcb" K = 2 Output : 6 Here, Given string is repeated 2 times and we get a new string "abcbabcb" Below are 6 occurren
10 min read
What are Subsequences in an Array? Subsequences are a fundamental concept in computer science and programming when working with arrays. A subsequence of an array is a sequence of elements from the array that appear in the same order, but not necessarily consecutively. In this blog post, we'll discuss subsequences, covering their defi
6 min read
String, Subsequence & Substring What is a Substring? A substring is a contiguous part of a string, i.e., a string inside another string. In general, for an string of size n, there are n*(n+1)/2 non-empty substrings. For example, Consider the string "geeks", There are 15 non-empty substrings. The subarrays are: g, ge, gee, geek, ge
6 min read