Dada una string str , la tarea es imprimir todas las subsecuencias de str .
Una subsecuencia es una secuencia que se puede derivar de otra secuencia eliminando algunos o ningún elemento sin cambiar el orden de los elementos restantes.
Ejemplos:
Entrada: str = “abc”
Salida: ab ab c ac bc abc
Entrada: str = “geek”
Salida: ge ge e ge ee gee k gk ek gek ek gek eek geek
Enfoque: escriba una función recursiva que imprima cada subsecuencia de la substring a partir del segundo carácter str[1, n – 1] después de agregar el primer carácter de la string str[0] al comienzo de cada subsecuencia . La condición de terminación será cuando la string pasada esté vacía, en ese caso la función devolverá una lista de arrays vacía .
A continuación se muestra la implementación del enfoque anterior:
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
// 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)); } }
Python3
# 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#
// 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
Javascript
<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>
g e ge e ge ee gee k gk ek gek ek gek eek geek
Solución alternativa: corrija los caracteres uno por uno y genere recursivamente todos los subconjuntos a partir de ellos.
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
// 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
# 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#
// 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
Javascript
<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>
c b bc a ac ab abc