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!

POWERLEX

Last Updated on March 22, 2022 by Ria Pathak

Recursion

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 2N

SOLVING APPROACH:

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.

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);
}
}
```
```def powerSet(s, cur = "", index = -1):

n = len(s)
if(index == n):
return

print(cur)

for i in range(index + 1, n):
cur = cur + s[i]
powerSet(s,cur,i)
cur = cur[:len(cur)-1]

s = list(input())
s.sort()
powerSet(s)
```

[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.