Last Updated on March 22, 2022 by Ria Pathak
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
SwithNelements, number of elements inP(S)is 2N
SOLVING APPROACH:
The idea is to fix a
prefix, then generate all subsets beginning with currentprefix.Once all subsets with a
prefixare generated, replace last character with one of the remaining characters to consider a differentprefixof 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.