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!






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 *