CONCEPTS USED:

Recursion

DIFFICULTY LEVEL:

Hard

PROBLEM STATEMENT(SIMPLIFIED):

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

OBSERVATION :

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

SOLVING APPROACH:

  1. The idea is to go through the best online c programming course and 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.

SOLUTIONS:

#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);
        dest++;
    }

    // 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 ;
  cout<<cur<<"\n";

  for(int i = index+1; i<n; i++){
    cur += s[i];
    powerSet(s,cur,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;
  sort(str.begin(),str.end());
  powerSet(str);

  return 0;
}
import java.util.*;
import java.io.*;

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 
        Arrays.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 ;
    System.out.println(cur);

    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 */
      powerSet(s,cur,i);
      cur = cur.substring(0, cur.length() - 1); 
    }
}
  public static void main(String args[]) throws IOException {
    Scanner sc = new Scanner(System.in);
    String str = sc.next();
    str = sortString(str);
    String cur = "";
    int index = -1;
    powerSet(str,cur,index);
  }
}

Previous post Mike and Exam
Next post Total number of ways to form a team of size K from X men and Y women with at least 4 men and 1 woman in the team

Leave a Reply

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