Given a string (lets say of length n), print all the subsequences of the given string.
Subsequences contain all the strings of length varying from 0 to n. But the order of characters should remain same as in the input string.
Note :
The order of subsequences are not important. Print every subsequence in new line.
The input only consists of one line which consists of a single string
The output consists of all subsequences of the input string where each subsequence is printed in a different line. The order of the subsequences doesn't matter
1 <= |S| <= 15
where |S| represents the length of the input string
Time limit: 1 sec
abc
"" (the double quotes just signifies an empty string, don't worry about the quotes)
c
b
bc
a
ac
ab
abc
All tags
Sort by
Interview problems
✅SIMPLE RECURSION🔥
#include<vector>
#include<bits/stdc++.h>
void solve(vector<char> &v,int n,int idx,vector<char> temp){
if(idx==n){
for(char c:temp){
cout<<c;
}
cout<<endl;
return;
}
solve(v,n,idx+1,temp);
temp.push_back(v[idx]);
solve(v,n,idx+1,temp);
}
void printSubsequences(char input[]) {
// Write your code here
vector<char> v;
int size=strlen(input);
for(int i=0;i<size;i++){
v.push_back(input[i]);
}
vector<char> temp;
solve(v,size,0,temp);
}
Interview problems
JAVA RECURSIVE SOLUTION
public class solution {
public static void printSubsequences(String input) {
// Write your code here
String ans="";
print(input,ans);
}
public static void print(String input,String ans){
if(input.length()==0){
System.out.println(ans);
return;
}
char ch=input.charAt(0);
String rstr=input.substring(1);
print(rstr , ans+ "");
print(rstr , ans+ ch);
}
}
Interview problems
Use recursion and do nothing
public static void solve(String s, String str, int i){
if(i == s.length()){
System.out.println(str);
return;
}
//exclude
solve(s, str, i+1);
//include
String k = str+s.charAt(i);
solve(s, k, i+1);
}
public static void printSubsequences(String input) {
// Write your code here
solve(input, "", 0);
}
Interview problems
Java Solution | Recursion.
import java.util.*;
public class solution {
public static void printSubsequences(String input) {
// Write your code here
ArrayList<Character> arr=new ArrayList<>();
Subsequences(0,input,arr);
}
public static void Subsequences(int i,String input,ArrayList<Character> arr)
{
if(i==input.length())
{
for(int j=0;j<arr.size();j++)
{
System.out.print(arr.get(j));
}
System.out.println();
return;
}
arr.add(input.charAt(i));
Subsequences(i+1,input,arr);
arr.remove(arr.size()-1);
Subsequences(i+1,input,arr);
}
}
Interview problems
easy recursion solution inc++
#include<bits/stdc++.h>
void all(int ind, vector<char>& as, char input[], int s) {
if (ind == s) {
for (char it : as) {
cout << it << "";
}
cout << endl;
return;
}
all(ind + 1, as, input, s);
as.push_back(input[ind]);
all(ind + 1, as, input, s);
as.pop_back();
}
void printSubsequences(char input[]) {
int s=strlen(input);
vector<char> as;
all(0,as,input,s);
}
Interview problems
c++ recursive code
#include<bits/stdc++.h>
void helper(char input[],string output){
if(strlen(input) == 0){
cout<<output<<endl;
return;
}
helper(input+1,output);
helper(input+1,output+input[0]);
}
void printSubsequences(char input[]) {
// Write your code here
string output;
helper(input,output);
}
Interview problems
C++ easy| clean code
#include<bits/stdc++.h>
void printF(int ind, vector<int>& dp,char input[], int n)
{
if(ind == n)
{
for(char it : dp)
{
cout<<it<<"";
}
cout <<endl;
return;
}
//not take
printF(ind+1,dp,input,n);
//take
dp.push_back(input[ind]);
printF(ind+1,dp,input,n);
dp.pop_back();
}
void printSubsequences(char input[]) {
// Write your code here
int n = strlen(input);
vector<int> dp;
printF(0,dp,input,n);
return;
}
Interview problems
easy sol c++
#include<bits/stdc++.h>
void solve(int i,char input[],string op,int s){
if(i>=s){
cout<<op<<"";
cout<<endl;
return ;
}
solve(i+1, input, op,s);
op.push_back(input[i]);
solve(i+1, input, op,s);
}
void printSubsequences(char input[]) {
string op="";
int s = strlen(input);
solve(0,input,op,s);
}
Interview problems
printSubsequences
public class solution {
public static void printSubsequences1(String input, String stringSoFar) {
if(input.length() == 0) { System.out.println(stringSoFar); return; }
String smallOuString = input.substring(1);
printSubsequences1(smallOuString, stringSoFar);
printSubsequences1(smallOuString, stringSoFar + input.charAt(0)); }
public static void printSubsequences(String input) { // Write your code here printSubsequences1(input,"");
} }
Interview problems
Java Solution using Recursion
import java.sql.Array;
import java.util.*;
public class solution {
static void print(int i,String str,List<List<Character>> ans,ArrayList<Character> al,int n){
if(i==n){
ans.add(new ArrayList<>(al));
return;
}
al.add(str.charAt(i));
print(i+1, str,ans,al,n);
al.remove(al.size()-1);
print(i+1, str,ans,al,n);
}
public static void printSubsequences(String input) {
// Write your code here
List<List<Character>> ans=new ArrayList<>();
ArrayList<Character> al=new ArrayList<>();
int n=input.length();
print(0,input,ans,al,n);
for(int j=0;j<ans.size();j++){
for(int k=0;k<ans.get(j).size();k++ ){
System.out.print(ans.get(j).get(k));
}
System.out.println();
}
}
}
