Print All Subsequences of a String

Problem Statement

Given a string, print all its possible subsequences. A subsequence is a sequence that can be derived from another sequence by deleting some or no elements without changing the order of the remaining elements.

Theory

Subarray

• A subarray is a contiguous part of an array.
• The elements of a subarray must appear consecutively in the original array.
• The order of the elements in the subarray must be the same as the order in the original array.

Example:

Array = {1, 2, 3}

The possible subarrays are:
{1}
{2}
{3}
{1, 2}
{2, 3}
{1, 2, 3}

Key Points:

• Subarrays are always contiguous.
• The number of subarrays of an array of size n is (n*(n+1)) / 2 (since for each start point, you can create different subarrays by expanding the endpoint).

Subsequence

• A subsequence is a sequence that can be derived from another sequence by deleting some (or no) elements without changing the order of the remaining elements.
• Elements of a subsequence do not have to be contiguous, but they must appear in the same relative order as in the original sequence.

Example:

Array = {1, 2, 3}

The possible subsequences are:

{}
{1}
{2}
{3}
{1, 2}
{1, 3}
{2, 3}
{1, 2, 3}

Key Points:

• The subsequences can be formed by keeping or removing the elements while maintaining order.
• The number of subsequences of a sequence of size n is 2^n (including the empty subsequence).

Subset

• A subset refers to any selection of elements from a set, where the order of elements does not matter.
• Subsets can be formed by choosing any combination of elements from the set.
• In set theory, all subsequences of a set are also subsets, but subsets ignore the order.

Example:

Array = {1, 2, 3}

The Possible subsets are:

{}
{1}
{2}
{3}
{1, 2}
{1, 3}
{2, 3}
{1, 2, 3}

Key Points:

• The order of elements does not matter in subsets (i.e., {1, 2} is the same as {2, 1}).
• The number of subsets of a set of size n is 2^n, same as subsequences.

Differences

Examples

Example 1:

Input: str = "abc"
Output:

a
b
c
ab
ac
bc
abc

Example 2:

Input: str = "abcd"
Output:

a
b
c
d
ab
ac
ad
bc
bd
cd
abc
abd
acd
bcd
abcd

Key Points:

• A subsequence includes any sequence derived by removing some or no characters from the original string while preserving the relative order of the characters.
• There are 2^n possible subsequences of a string of length n because each character can either be included or excluded from the subsequence.

Different Approaches

1️⃣ Iterative Approach

To generate all subsequences using an iterative approach, we can use the concept of bitmasking. Each subsequence can be represented by a binary number, where each bit in the number corresponds to an element in the sequence:

• A 1 means the element is included in the subsequence.
• A 0 means the element is excluded.

For a sequence of length n, there are 2^n possible subsequences. We can iterate through all possible numbers from 0 to (2^n)-1 and use the binary representation of these numbers to decide which elements to include in each subsequence.

Code:

#include <iostream>
#include <vector>
#include <string>

using namespace std;

int main()
{
    string str = "abc";
    vector<string> ans;
    
    int n = str.size();
    
    int totalSubsequences = 1 << n; // This is 2^n, total number of subsequences
    
    for (int mask = 0; mask < totalSubsequences; mask++) {
    
        string subsequence = "";
        for(int i = 0; i < n; i++) {
            // Check if the i-th bit in mask is set.
            if (mask & (1 << i)) {
                subsequence += str[i];
            }
        }
        ans.push_back(subsequence);
    }
    
    for(auto strItr: ans) {
        cout << strItr << endl;
    }

}

Output:

a
b
ab
c
ac
bc
abc

Complexity Analysis:

• Time Complexity: O(n * 2^n)
  • We generate 2^n subsequences.
  • For each subsequences, we iterate through the original string of length n.
• Space Complexity: O(n * 2^n)
  • Auxiliary Space: Space required by the algorithm itself (other than the input data) which is for the bit-masking process O(n), since we store at most n characters in subsequence during each iteration.
  • Output Space: Space used to store the subsequences.

2️⃣ Recursion

Recursive Approach:

1. For each element in the sequence, there are two choices:
   • Include the current element in the subsequence.
   • Exclude the current element from the subsequence.
2. Recursively generate subsequences for the remaining part of the sequence.
3. Base case: When you reach the end of the sequence, return the generated subsequence. When input becomes empty.

Visualization of Recursive Tree:

For the input string ABC, the recursive process can be visualized as a decision tree where each node represents a decision to either include or exclude a character.

                               ""
                              /  \
                   Exclude 'A'     Include 'A'
                          /              \
                      ""                "A"
                     /  \               /  \
          Exclude 'B'   Include 'B'  Exclude 'B'  Include 'B'
               /              \            /              \
            ""               "B"         "A"            "AB"
           /   \            /    \       /    \          /   \
   Exclude 'C' Include 'C' Exclude Include Exclude Include Exclude Include
       |           |        |        |       |        |       |        |
      ""          "C"      "B"      "BC"     "A"     "AC"     "AB"    "ABC"

• At each level of the tree, we either exclude or include the current character.
• As we traverse down the tree, we accumulate the characters that form the subsequences.

Visualization for numbers:

nums = {1, 2, 3}

                                 []
                               /    \
                          Exclude 1  Include 1
                             /            \
                          []              [1]
                         /   \           /   \
                  Exclude 2  Include 2 Exclude 2  Include 2
                    /         \         /         \
                 []         [2]      [1]         [1, 2]
                /  \       /    \     /   \      /     \
       Exclude 3 Include 3 Exclude Include Exclude  Include
           |          |        |       |       |          |
          []        [3]      [2]    [2,3]    [1]       [1, 3]
                                               /  \
                                          Exclude  Include
                                             |        |
                                            [1]    [1, 3]

Explanation:

1. Initial Node: The root of the tree starts with an empty string "".
   • Left Child: Represents excluding the character 'A'.
   • Right Child: Represents including the character 'A'.
2. Next Level (processing 'B'):
   • For each subsequent level:
     • Left Child: Represents excluding the current character (here 'B').
     • Right Child: Represents including the current character.
3. Final Level (processing 'C'):
   • At the final level, when we reach the last character 'C':
     • The left child represents excluding 'C'.
     • The right child represents including 'C'.
   • This produces the final set of subsequences.

Code:

#include <iostream>
#include <vector>
#include <string>

void findSubsequences(std::string str, int index, std::string current) {
    // Base case: If we have processed all characters
    if (index == str.size()) {
        std::cout << current << "\n";  // Print the current subsequence
        return;
    }

    // Recursive case 1: Exclude the current character and move to the next
    findSubsequences(str, index + 1, current);

    // Recursive case 2: Include the current character and move to the next
    current.push_back(str[index]);
    findSubsequences(str, index + 1, current);
}

int main() {
    std::string input = "ABC";
    std::cout << "All subsequences of " << input << " are:\n";
    findSubsequences(input, 0, "");
    return 0;
}

Another Code:

#include <iostream>
#include <vector>

using namespace std;

class Solution {
private:
    void func(int ind, int n, vector<int> &nums, vector<int> &arr, vector<vector<int>> &ans) {
        // Base case: if the index reaches the length of the array,
        // add the current subset to the answer list
        if (ind == n) {
            ans.push_back(arr);
            return;
        }

        // Recursive case: Exclude the current element and move to the next element
        func(ind + 1, n, nums, arr, ans);

        // Include the current element in the subset and move to the next element
        arr.push_back(nums[ind]);
        func(ind + 1, n, nums, arr, ans);

        // Backtrack: remove the last added element to explore other subsets
        arr.pop_back();
    }

public:
    vector<vector<int>> powerSet(vector<int> &nums) {
        vector<vector<int>> ans;  // List to store all subsets
        vector<int> arr;  // Temporary list to store the current subset
        func(0, nums.size(), nums, arr, ans);  // Start the recursive process
        return ans;  // Return the list of all subsets
    }
};

// Main method to test the code
int main() {
    Solution sol;
    vector<int> nums = {1, 2, 3};
    vector<vector<int>> result = sol.powerSet(nums);
    
    // Print the result
    for (const auto &subset : result) {
        cout << "[";
        for (int num : subset) {
            cout << num << " ";
        }
        cout << "]" << endl;
    }

    return 0;
}

Passing by Value Array:

#include <iostream>
#include <vector>

using namespace std;

class Solution {
private:
    void func(int ind, int n, vector<int> &nums, vector<int> arr, vector<vector<int>> &ans) {
        // Base case: if the index reaches the length of the array,
        // add the current subset to the answer list
        if (ind == n) {
            ans.push_back(arr);
            return;
        }

        // Recursive case: Exclude the current element and move to the next element
        func(ind + 1, n, nums, arr, ans);

        // Include the current element in the subset and move to the next element
        arr.push_back(nums[ind]);
        func(ind + 1, n, nums, arr, ans);

        // Backtrack: remove the last added element to explore other subsets
        // arr.pop_back();
    }

public:
    vector<vector<int>> powerSet(vector<int> &nums) {
        vector<vector<int>> ans;  // List to store all subsets
        vector<int> arr;  // Temporary list to store the current subset
        func(0, nums.size(), nums, arr, ans);  // Start the recursive process
        return ans;  // Return the list of all subsets
    }
};

// Main method to test the code
int main() {
    Solution sol;
    vector<int> nums = {1, 2, 3};
    vector<vector<int>> result = sol.powerSet(nums);
    
    // Print the result
    for (const auto &subset : result) {
        cout << "[";
        for (int num : subset) {
            cout << num << " ";
        }
        cout << "]" << endl;
    }

    return 0;
}

Notice that arr is passed by value, not by reference. This means that every time func is called, a new copy of arr is created. Consequently:

• Modifying arr (such as by adding elements using arr.push_back()) does not affect the original arr used in the previous recursive calls.
• As a result, when you add or modify arr within a recursive call, it only affects that specific call's copy of arr.

Because arr is being passed by value, you don't need to use arr.pop_back() to backtrack. Each recursive call gets its own separate copy of arr, so changes made to arr in one call don’t affect the arr used in other calls.

Another Code:

#include <iostream>
using namespace std;

void printSubsequences(string ip, string op) {
    // Base Case: If the input string is empty, print the current output
    if (ip.empty()) {
        cout << op << endl;
        return;
    }

    // Choice 1: Exclude the current character from the output
    printSubsequences(ip.substr(1), op);

    // Choice 2: Include the current character in the output
    printSubsequences(ip.substr(1), op + ip[0]);
}

int main() {
    string input;
    cout << "Enter a string: ";
    cin >> input;

    // Initial call with the full input and an empty output
    printSubsequences(input, "");
    return 0;
}

Complexity Analysis:

• Time Complexity: O(2^n)
  • Each element in the array has two choices:
    • Either to included in a subset or not, leading to 2^n possible subsets.
• Space Complexity: O(n * 2^n)
  • We generate 2^n subsets, and each subsets can have up to n elements. Additionally, the recursion stack can go up to a depth of n.