How to Generate All Subsequences of a String in Java or C++?

How can I obtain all possible subsequence combinations of a string in Java or C++?

A subsequence of a string is a new string that is formed from the original string by deleting some characters without changing the order of the remaining characters. This article explains how to generate all subsequences of a given string in popular programming languages like Java and C++.

// Java implementation to generate all subsequences of a string
public class Subsequences {
    public static void main(String[] args) {
        String str = "abc";
        generateSubsequences(str, "");
    }

    public static void generateSubsequences(String str, String current) {
        if (str.length() == 0) {
            System.out.println(current);
            return;
        }
        // Exclude current character
        generateSubsequences(str.substring(1), current);
        // Include current character
        generateSubsequences(str.substring(1), current + str.charAt(0));
    }
} // Output: a, b, c, ab, ac, bc, abc, 

// C++ implementation to generate all subsequences of a string
#include <iostream>
#include <string>
using namespace std;

void generateSubsequences(string str, string current, int index) {
    if (index == str.length()) {
        cout << current << endl;
        return;
    }
    // Exclude current character
    generateSubsequences(str, current, index + 1);
    // Include current character
    generateSubsequences(str, current + str[index], index + 1);
}

int main() {
    string str = "abc";
    generateSubsequences(str, "", 0);
    return 0;
} // Output: a, b, c, ab, ac, bc, abc, 

Causes

• Understanding the difference between subsequences and substrings.
• Not accounting for empty subsequences which are valid.
• Overlooking duplicate characters affecting the output.

Solutions

• Use recursion to generate subsequences efficiently.
• Utilize bit manipulation for a more concise solution.
• Implement an iterative approach using loops.

Mistake: Not handling the empty subsequence case correctly.

Solution: Ensure to include logic in your function to print the current subsequence even if it's empty.

Mistake: Using complicated loops instead of recursion for this problem.

Solution: Utilize recursion or bit manipulation to simplify subsequence generation.