Imprime todas las strings posibles que se pueden hacer colocando espacios

Dada una string, debe imprimir todas las strings posibles que se pueden formar colocando espacios (cero o uno) entre ellas 

Ejemplos: 

Input :  str[] = "ABC"
Output : ABC
         AB C
         A BC
         A B C

Input : str[] = "ABCD"
Output : ABCD
         A BCD
         AB CD
         A B CD
         ABC D
         A BC D
         AB C D
         A B C D

Si observamos más de cerca, podemos notar que este problema se reduce al problema de Power Set . Básicamente necesitamos generar todos los subconjuntos donde cada elemento es un espacio diferente.  

Implementación:

// C++ program to print all strings that can be
// made by placing spaces
#include <bits/stdc++.h>
using namespace std;
 
void printSubsequences(string str)
{
    int n = str.length();
    unsigned int opsize = pow(2, n - 1);
 
    for (int counter = 0; counter < opsize; counter++) {
        for (int j = 0; j < n; j++) {
 
            cout << str[j];
            if (counter & (1 << j))
                cout << " ";
        }
        cout << endl;
    }
}
 
// Driver code
int main()
{
    string str = "ABC";
    printSubsequences(str);
    return 0;
}

// Java program to print all strings that can be
// made by placing spaces
import java.util.*;
class GFG
{
static void printSubsequences(String s)
{
    char[] str= s.toCharArray();
    int n = str.length;
    int opsize = (int)(Math.pow(2, n - 1));
 
    for (int counter = 0; counter < opsize; counter++) {
        for (int j = 0; j < n; j++) {
 
            System.out.print(str[j]);
            if ((counter & (1 << j)) > 0)
                System.out.print(" ");
        }
        System.out.println();
    }
}
 
// Driver code
public static void main(String[] args)
{
    String str = "AB";
    printSubsequences(str);
}
}
 
/* This code is contributed by Mr. Somesh Awasthi */

# Python 3 program to print all strings
# that can be made by placing spaces
from math import pow
 
def printSubsequences(str):
    n = len(str)
    opsize = int(pow(2, n - 1))
 
    for counter in range(opsize):
        for j in range(n):
            print(str[j], end = "")
            if (counter & (1 << j)):
                print(" ", end = "")
 
        print("\n", end = "")
 
# Driver code
if __name__ == '__main__':
    str = "ABC"
    printSubsequences(str)
 
# This code is contributed by
# Sanjit_Prasad

// C# program to print all strings
// that can be made by placing spaces
using System;
 
class GFG {
     
    // Function to print all subsequences
    static void printSubsequences(String s)
    {
        char[] str= s.ToCharArray();
        int n = str.Length;
        int opsize = (int)(Math.Pow(2, n - 1));
     
        for (int counter = 0; counter < opsize;
                                     counter++)
        {
            for (int j = 0; j < n; j++)
            {
                Console.Write(str[j]);
                 
                if ((counter & (1 << j)) > 0)
                    Console.Write(" ");
            }
            Console.WriteLine();
        }
    }
     
    // Driver code
    public static void Main()
    {
        String str = "ABC";
        printSubsequences(str);
    }
}
 
// This code is contributed by shiv_bhakt.

<?php
// PHP program to print
// all strings that can be
// made by placing spaces
 
function printSubsequences($str)
{
    $n = strlen($str);
    $opsize = pow(2, $n - 1);
 
    for ($counter = 0;
         $counter < $opsize;
         $counter++)
    {
        for ($j = 0; $j < $n; $j++)
        {
            echo $str[$j];
            if ($counter & (1 << $j))
                echo " ";
        }
        echo "\n";
    }
}
 
// Driver code
$str = "ABC";
printSubsequences($str);
 
// This code is contributed by ajit
?>

<script>
 
// Javascript program to print all strings
// that can be made by placing spaces
 
// Function to print all subsequences
function printSubsequences(s)
{
    let str= s.split('');
    let n = str.length;
    let opsize = Math.pow(2, n - 1);
   
    for(let counter = 0; counter < opsize; counter++)
    {
        for(let j = 0; j < n; j++)
        {
            document.write(str[j]);
               
            if ((counter & (1 << j)) > 0)
                document.write(" ");
        }
        document.write("</br>");
    }
}
 
// Driver code
let str = "ABC";
printSubsequences(str);
 
// This code is contributed by rameshtravel07
</script>

ABC
A BC
AB C
A B C

Complejidad de tiempo : O(n*2 ^n-1 ) 
Espacio auxiliar : O(1)

Preguntado en: Amazon
Este artículo es una contribución de Jebasingh y Ninja. 

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 review-team@geeksforgeeks.org. Vea su artículo que aparece en la página principal de GeeksforGeeks y ayude a otros Geeks.