Q:

Program to find all possible subsets of a string

belongs to collection: String Programs

0

Explanation

In this program, all the subsets of the string need to be printed. The subset of a string is the character or the group of characters that are present inside the string. For example, all possible subsets of a string "FUN" will be F, U, N, FU, UN, FUN.

To complete this program, We need to run two for loops. The outer loop is used to maintain the relative position of the first character and the second loop is used to create all possible subsets and prints them one by one.

The algorithm of the program is given below.

Algorithm

  1. Define a string.
  2. All the possible subsets for a string will be n*(n + 1)/2.
  3. Define a string array with the length of n(n+1)/2. This string array will hold all the subsets of the string.
  4. The first loop will keep the first character of the subset.
  5. The second loop will build the subset by adding one character in each iteration till the end of the string is reached.
    Eg. String "ABC"
    The first loop will hold the position of A, then B then C
    The second loop will subset the string into
    For i=1: A, AB then ABC for the last iteration
    For i=2: B and BC
    For i=3: C
  6. Add the subset formed in each iteration into a string array.
  7. The last loop traverses through all the subset formed and print all the subsets.

Input:

str = "ABC"  

Output:

All subsets for given string are:
A
AB
ABC
B
BC
C

All Answers

need an explanation for this answer? contact us directly to get an explanation for this answer

Python

str = "ABC";  
n = len(str);  
#For holding all the formed substrings  
arr = [];  
   
#This loop maintains the starting character  
for i in range(0,n):  
    #This loop will add a character to start character one by one till the end is reached  
    for j in range(i,n):  
        arr.append(str[i:(j+1)]);  
   
#Prints all the subset  
print("All subsets for given string are: ");  
for i in arr:  
    print(i);  

 

Output:

All subsets for given string are: 
A
AB
ABC
B
BC
C

 

C

#include <stdio.h>  
#include <string.h>  
   
//User-defined substring function that will take string(str), position(p) and no of character(len) as input  
//Produces result c as output  
void substring(char s[], char sub[], int p, int len){  
   int c = 0;  
   while (c < len) {  
      sub[c] = s[p+c];  
      c++;  
   }  
   sub[c] = '\0';  
}  
   
int main()  
{  
    char c[10],str[10] ="ABC";  
    int i, j, len = strlen(str);  
      
    printf("All subsets for the given string are: ");  
    //This loop maintains the starting character  
    for(i = 0; i < len; i++){  
        //This loop adds the next character every iteration for the subset to form and add it to the array  
        for(j = 1; j <= len-i; j++){  
            substring(str,c,i,j);  
            printf("%s\n",c);  
        }  
    }  
    return 0;  
}  

 

Output:

All subsets for given string are: 
A
AB
ABC
B
BC
C

 

JAVA

public class AllSubsets {  
    public static void main(String[] args) {  
          
        String str = "ABC";  
        int len = str.length();  
        int temp = 0;  
        //Total possible subsets for string of size n is n*(n+1)/2  
        String arr[] = new String[len*(len+1)/2];  
          
        //This loop maintains the starting character  
        for(int i = 0; i < len; i++) {  
            //This loop adds the next character every iteration for the subset to form and add it to the array  
            for(int j = i; j < len; j++) {  
                arr[temp] = str.substring(i, j+1);  
                temp++;  
            }  
        }  
          
        //This loop prints all the subsets formed from the string.  
        System.out.println("All subsets for given string are: ");  
        for(int i = 0; i < arr.length; i++) {  
            System.out.println(arr[i]);  
        }  
    }  
}  

 

Output:

All subsets for given string are: 
A
AB
ABC
B
BC
C

 

C#

using System;                      
public class Program  
{  
    public static void Main()  
    {  
        string str = "ABC";  
        int len = str.Length;  
        int temp = 0;  
          
        //Total possible subsets for string of size n is n*(n+1)/2  
        String[] arr = new String[len*(len+1)/2];  
          
        //This loop maintains the starting character  
        for(int i = 0; i < len; i++) {  
            //This loop adds the next character every iteration for the subset to form and add it to the array  
            for(int j = 0; j < len-i; j++) {  
                arr[temp] = str.Substring(i,j+1);  
                temp++;  
            }  
        }  
          
        //This loop prints all the subsets formed from the string.  
        Console.WriteLine("All subsets for given string are : ");  
        for(int i = 0; i < arr.Length; i++) {  
            Console.WriteLine(arr[i]);  
        }  
    }  
}    

         

 

Output:

All subsets for given string are: 
A
AB
ABC
B
BC
C

 

PHP

<!DOCTYPE html>   
<html>   
<body>   
<?php   
    $str1 = "ABC";   
    $len = strlen($str1);  
    $arr = array();  
      
    //This loop maintains the starting character  
    for($i = 0; $i < $len; $i++){  
 //This loop adds the next character every iteration for the subset to form and add it to the array  
        for($j = 0; $j < $len - $i; $j++){  
            array_push($arr,substr($str1,$i,($j+1)));  
        }  
    }  
      
    echo "All subsets for given string are: ";  
    foreach($arr as $v){   
        echo "<br> $v";  
    }  
?>   
</body>   
</html>   

 

Output:

All subsets for given string are: 
A
AB
ABC
B
BC
C

need an explanation for this answer? contact us directly to get an explanation for this answer

total answers (1)

This question belongs to these collections

Similar questions


Program to find the longest repeating sequence in ... >>
<< Program to find all the permutations of a string...