« Return subsequences of a string

Problem

Given a string, we have to find out all subsequences of it. A String is a subsequence of a given String, that is generated by deleting some character of a given string without changing its order.

Input Format:

A string

Output Format:

Print all the subsequences of a string in different lines

Sample Input :

abc

Sample Output :

""

a

b

c

ab

bc

ac

abc

Solution

Copy
1#include <iostream>
2#include <iomanip>
3#include <algorithm>
4#include <string>
5#include <cstring>
6#include <vector>
7#include <cmath>
8#include <map>
9#include <climits>
10// climits for INT_MIN
11#include <unordered_map>
12using namespace std;
13
14int subs(string input, string output[])
15{
16    if (input.empty())
17    {
18        output[0] = "";
19        return 1;
20    }
21
22    string smallString = input.substr(1);
23    int smallOutputSize = subs(smallString, output);
24    for (int i = 0; i < smallOutputSize; i++)
25    {
26        output[i + smallOutputSize] = input[0] + output[i];
27    }
28    return 2 * smallOutputSize;
29}
30
31int main()
32{
33    /*
34    abc ["", a, b, c, ab, bc, ac, abc]
35
36    pow(2, n) is total number of subsequences.
37
38    As for every character we have to make
39    a choice whether to include or not
40    include the character.
41
42    difference between subsequences and substrings:
43    substrings are continuous.
44    For subsequences we can pick any characters
45    */
46
47    string input;
48    cin >> input;
49    int x = pow(2, input.size());
50
51    string *output = new string[x];
52    int count = subs(input, output);
53
54    for (int i = 0; i < count; i++)
55    {
56        cout << output[i] << endl;
57    }
58    return 0;
59}