Dada una string de entrada de números, encuentra todas las combinaciones de números que se pueden formar usando dígitos en el mismo orden.
Ejemplos:
Input : 123 Output :1 2 3 1 23 12 3 123 Input : 1234 Output : 1 2 3 4 1 2 34 1 23 4 1 234 12 3 4 12 34 123 4 1234
El problema se puede resolver mediante recursividad. Realizamos un seguimiento del índice actual en la string de entrada dada y la longitud de la string de salida hasta el momento. En cada llamada a la función, si no quedan dígitos en la string de entrada, imprima la string de salida actual y regrese. De lo contrario, copie el dígito actual a la salida. Desde aquí, haga dos llamadas, una que considere el siguiente dígito como parte del siguiente número (incluido un espacio en la string de salida) y otra que considere el siguiente dígito como parte del número actual (sin espacio incluido). Si no quedan dígitos después del dígito actual, se omite la segunda llamada a la función porque un espacio final no cuenta como una nueva combinación.
C++
// CPP program to find all combination of numbers // from a given string of digits #include <iostream> #include <cstring> using namespace std; // function to print combinations of numbers // in given input string void printCombinations(char* input, int index, char* output, int outLength) { // no more digits left in input string if (input[index] == '\0') { // print output string & return output[outLength] = '\0'; cout << output << endl; return; } // place current digit in input string output[outLength] = input[index]; // separate next digit with a space output[outLength + 1] = ' '; printCombinations(input, index + 1, output, outLength + 2); // if next digit exists make a // call without including space if(input[index + 1] != '\0') printCombinations(input, index + 1, output, outLength + 1); } // driver function to test above function int main() { char input[] = "1214"; char *output = new char[100]; // initialize output with empty string output[0] = '\0'; printCombinations(input, 0, output, 0); return 0; }
Java
// Java program to find all combinations // of numbers from a given string of digits class GFG { // function to print combinations of numbers // in given input string static void printCombinations(char[] input, int index, char[] output, int outLength) { // no more digits left in input string if (input.length == index) { // print output string & return System.out.println(String.valueOf(output)); return; } // place current digit in input string output[outLength] = input[index]; // separate next digit with a space output[outLength + 1] = ' '; printCombinations(input, index + 1, output, outLength + 2); // if next digit exists make a // call without including space if(input.length!=index + 1) printCombinations(input, index + 1, output, outLength + 1); } // Driver Code public static void main(String[] args) { char input[] = "1214".toCharArray(); char []output = new char[100]; printCombinations(input, 0, output, 0); } } // This code is contributed by Rajput-Ji
Python3
# Python3 program to find all combination of numbers # from a given string of digits # function to print combinations of numbers # in given input string def printCombinations(input, index, output, outLength): # no more digits left in input string if (len(input) == index): # print output string & return output[outLength] = '\0' print(*output[:outLength], sep = "") return # place current digit in input string output[outLength] = input[index] # separate next digit with a space output[outLength + 1] = ' ' printCombinations(input, index + 1, output, outLength + 2) # if next digit exists make a # call without including space if(len(input) != (index + 1)): printCombinations(input, index + 1, output, outLength + 1) # Driver code input = "1214" output = [0]*100 # initialize output with empty string output[0] = '\0' printCombinations(input, 0, output, 0) # This code is contributed by SHUBHAMSINGH10
C#
// C# program to find all combinations // of numbers from a given string of digits using System; class GFG { // function to print combinations of numbers // in given input string static void printCombinations(char[] input, int index, char[] output, int outLength) { // no more digits left in input string if (input.Length == index) { // print output string & return Console.WriteLine(String.Join("", output)); return; } // place current digit in input string output[outLength] = input[index]; // separate next digit with a space output[outLength + 1] = ' '; printCombinations(input, index + 1, output, outLength + 2); // if next digit exists make a // call without including space if(input.Length!=index + 1) printCombinations(input, index + 1, output, outLength + 1); } // Driver Code public static void Main(String[] args) { char []input = "1214".ToCharArray(); char []output = new char[100]; printCombinations(input, 0, output, 0); } } // This code is contributed by 29AjayKumar
Javascript
<script> // Javascript program to find all combinations // of numbers from a given string of digits // function to print combinations of numbers // in given input string function printCombinations(input,index,output,outLength) { // no more digits left in input string if (input.length == index) { // print output string & return document.write(output.join("")+"<br>"); return; } // place current digit in input string output[outLength] = input[index]; // separate next digit with a space output[outLength + 1] = ' '; printCombinations(input, index + 1, output, outLength + 2); // if next digit exists make a // call without including space if(input.length != index + 1) printCombinations(input, index + 1, output, outLength + 1); } // Driver Code let input = "1214".split(""); let output = new Array(100); printCombinations(input, 0, output, 0); // This code is contributed by avanitrachhadiya2155 </script>
Producción:
1 2 1 4 1 2 14 1 21 4 1 214 12 1 4 12 14 121 4 1214
Solución alternativa:
C++
// CPP program to find all combination of // numbers from a given string of digits // using bit algorithm used same logic // as to print power set of string #include <bits/stdc++.h> using namespace std; // function to print combinations of // numbers in given input string void printCombinations(char s[]){ // find length of char array int l = strlen(s); // we can give space between characters // ex. ('1' & '2') or ('2' & '3') or // ('3' & '4') or ('3' & '4') or all // that`s why here we have maximum // space length - 1 for(int i = 0; i < pow(2, l - 1); i++){ int k = i, x = 0; // first character will be printed // as well cout << s[x]; x++; for(int j = 0; j < strlen(s) - 1; j++){ // if bit is set, means provide // space if(k & 1) cout << " "; k = k >> 1; cout << s[x]; // always increment index of // input string x++; } cout << "\n"; } } // driver code int main() { char input[] = "1214"; printCombinations(input); return 0; } // This code is contributed by PRINCE Gupta 2
Java
// Java program to find all combination of // numbers from a given string of digits // using bit algorithm used same logic // as to print power set of string import java.util.*; class GFG { // function to print combinations of // numbers in given input string static void printCombinations(char s[]) { // find length of char array int l = s.length; // we can give space between characters // ex. ('1' & '2') or ('2' & '3') or // ('3' & '4') or ('3' & '4') or all // that`s why here we have maximum // space length - 1 for(int i = 0; i < Math.pow(2, l - 1); i++) { int k = i, x = 0; // first character will be printed // as well System.out.print(s[x]); x++; for(int j = 0; j < s.length - 1; j++) { // if bit is set, means provide // space if(k % 2 == 1) System.out.print(" "); k = k >> 1; System.out.print(s[x]); // always increment index of // input string x++; } System.out.print("\n"); } } // Driver Code public static void main(String[] args) { char input[] = "1214".toCharArray(); printCombinations(input); } } // This code is contributed by PrinciRaj1992
Python3
# Python 3 program to find all # combination of numbers from # a given string of digits using # bit algorithm used same logic # as to print power set of string # Function to print combinations of # numbers in given input string def printCombinations(s): # find length of char array l = len(s); # we can give space between # characters ex. ('1' & '2') # or ('2' & '3') or ('3' & '4') # or ('3' & '4') or all that`s # why here we have maximum # space length - 1 for i in range(pow(2, l - 1)): k = i x = 0 # first character will # be printed as well print(s[x], end = "") x += 1 for j in range(len(s) - 1): # if bit is set, means # provide space if(k & 1): print(" ", end = "") k = k >> 1 print(s[x], end = "") # always increment index of # input string x += 1 print() # Driver code if __name__ == "__main__": inp = "1214"; printCombinations(inp); # This code is contributed by Chitranayal
C#
// C# program to find all combination of // numbers from a given string of digits // using bit algorithm used same logic // as to print power set of string using System; class GFG { // function to print combinations of // numbers in given input string static void printCombinations(char []s) { // find length of char array int l = s.Length; // we can give space between characters // ex. ('1' & '2') or ('2' & '3') or // ('3' & '4') or ('3' & '4') or all // that`s why here we have maximum // space length - 1 for(int i = 0; i < Math.Pow(2, l - 1); i++) { int k = i, x = 0; // first character will be printed // as well Console.Write(s[x]); x++; for(int j = 0; j < s.Length - 1; j++) { // if bit is set, means provide // space if(k % 2 == 1) Console.Write(" "); k = k >> 1; Console.Write(s[x]); // always increment index of // input string x++; } Console.Write("\n"); } } // Driver Code public static void Main(String[] args) { char []input = "1214".ToCharArray(); printCombinations(input); } } // This code is contributed by Rajput-Ji
Javascript
<script> // Javascript program to find all combination of // numbers from a given string of digits // using bit algorithm used same logic // as to print power set of string // function to print combinations of // numbers in given input string function printCombinations(s) { // find length of char array let l = s.length; // we can give space between characters // ex. ('1' & '2') or ('2' & '3') or // ('3' & '4') or ('3' & '4') or all // that`s why here we have maximum // space length - 1 for(let i = 0; i < Math.pow(2, l - 1); i++) { let k = i, x = 0; // first character will be printed // as well document.write(s[x]); x++; for(let j = 0; j < s.length - 1; j++) { // if bit is set, means provide // space if(k % 2 == 1) document.write(" "); k = k >> 1; document.write(s[x]); // always increment index of // input string x++; } document.write("<br>"); } } // Driver Code let input= "1214".split(""); printCombinations(input); // This code is contributed by rag2127 </script>
Producción:
1214 1 214 12 14 1 2 14 121 4 1 21 4 12 1 4 1 2 1 4
Este artículo es una contribución de aditi sharma 2 . Si te gusta GeeksforGeeks y te gustaría contribuir, también puedes escribir un artículo usando write.geeksforgeeks.org o enviar tu artículo por correo a contribuido@geeksforgeeks.org. Vea su artículo que aparece en la página principal de GeeksforGeeks y ayude a otros Geeks.
Escriba comentarios si encuentra algo incorrecto o si desea compartir más información sobre el tema tratado anteriormente.
Publicación traducida automáticamente
Artículo escrito por GeeksforGeeks-1 y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA