Get free ebooK with 50 must do coding Question for Product Based Companies solved
Fill the details & get ebook over email
Thank You!
We have sent the Ebook on 50 Must Do Coding Questions for Product Based Companies Solved over your email. All the best!

Last Updated on March 22, 2022 by Ria Pathak






Given a string, write a recursive code to print all subsets of it. The subsets are to be printed in lexicographical(alphabetic) order.

For Example :

Input :  string = "abc"

Output : "", "a", "b", "c", "ab", "ac", "bc", "abc"

See original problem statement here


For a given set S with N elements, number of elements in P(S) is 2N


  1. The idea is to fix a prefix, then generate all subsets beginning with current prefix.

  2. Once all subsets with a prefix are generated, replace last character with one of the remaining characters to consider a different prefix of subsets.


#include <stdio.h>
#include <string.h>
#include <stdlib.h>

/* function for appending a char to a char array */
void append(char* s, char c) {
        int len = strlen(s);
        s[len] = c;
        s[len+1] = '\0';

// comparator function for qsort in c
int cmpfunc (const void * a, const void * b) {
   return ( *(char*)a - *(char*)b );

// Below function extracts characters present in src
// between m and n (excluding n) 
char* substr(const char *src, int m, int n)
    // get length of the destination string
    int len = n - m;

    // allocate (len + 1) chars for destination (+1 for extra null character)
    char *dest = (char*)malloc(sizeof(char) * (len + 1));

    // extracts characters between m'th and n'th index from source string
    // and copy them into the destination string
    for (int i = m; i < n && (*(src + i) != '\0'); i++)
        *dest = *(src + i);

    // null-terminate the destination string
    *dest = '\0';

    // return the destination string
    return dest - len;

void powerSet(char *s, char *cur, int index){

  int n = strlen(s);
  if(index == n)
    return ;

  printf("%s\n", cur);

  for(int i = index + 1; i<n; i++){

    /* creating a temporary char array */
    char temp[100];

    /* copying original char array to temp array */
    strcpy(temp, cur);

    /* append char s[i] to char array temp */
    append(temp, s[i]);

    /*append char s[i] to cur */
    append(cur, s[i]);

    powerSet(s, temp, i);
    /* After all subset beginning with "cur" are printed,
      we will remove the last character to consider different 
      prefix of subsets */
    cur = substr(cur, 0, strlen(cur) - 1);

int main()
  char str[100]; scanf("%s" ,str);

  //sorting all the characters of str in
  //non-decreasing order
  qsort(str, strlen(str), sizeof(char), cmpfunc);

  char res[100] = "";
  powerSet(str, res, -1);

  return 0;
#include <bits/stdc++.h>
using namespace std;

void powerSet(string s,string cur = "",int index = -1){
  int n = s.size();
  if(index == n)
    return ;

  for(int i = index+1; i<n; i++){
    cur += s[i];
    /* After all subset beginning with "cur" are printed,
      we will remove the last character to consider different 
      prefix of subsets */
    cur = cur.erase(cur.size()-1);
int main()
  string str;cin>>str;

  return 0;
import java.util.*;

public class Main {
    //Function of sorting a string 
  public static String sortString(String inputString){ 
        // convert input string to char array 
        char tempArray[] = inputString.toCharArray();
        // sort tempArray 
        // return new sorted string 
        return new String(tempArray); 
  static void powerSet(String s,String cur,int index){
    int n = s.length();
    if(index == n)
      return ;

    for(int i = index+1; i<n; i++){
      cur += s.charAt(i);
      /* After all subset beginning with "cur" are printed,
      we will remove the last character to consider different 
      prefix of subsets */
      cur = cur.substring(0, cur.length() - 1); 
  public static void main(String args[]) throws IOException {
    Scanner sc = new Scanner(;
    String str =;
    str = sortString(str);
    String cur = "";
    int index = -1;
def powerSet(s, cur = "", index = -1):
	n = len(s)
	if(index == n):
	for i in range(index + 1, n):
		cur = cur + s[i]
		cur = cur[:len(cur)-1]

s = list(input())

[forminator_quiz id="818"]

This article tried to discuss the concept of Recursion. Hope this blog helps you understand and solve the problem. To practice more problems on Recursion you can check out MYCODE | Competitive Programming.

Leave a Reply

Your email address will not be published. Required fields are marked *