Tutorialspoint.dev

Print all possible strings that can be made by placing spaces

Given a string you need to print all possible strings that can be made by placing spaces (zero or one) in between them
Examples :

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


If we take a closer look, we can notice that this problem boils down to Power Set problem. We basically need to generate all subsets where every element is a different space.

C++

// 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

// 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 */

/div>

Python3

# 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(" ", end = "") # Driver code if __name__ == '__main__': str = "ABC" printSubsequences(str) # This code is contributed by # Sanjit_Prasad [tabby title="C#"]

// 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
// 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 " ";
    }
}
  
// Driver code
$str = "ABC";
printSubsequences($str);
  
// This code is contributed by ajit
?>


Output :

ABC
A BC
AB C
A B C

Asked in:

Please write comments if you find anything incorrect, or you want to share more information about the topic discussed above.



This article is attributed to GeeksforGeeks.org

You Might Also Like

leave a comment

code

0 Comments

load comments

Subscribe to Our Newsletter