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