Print all subsequences of a string

Posted by N.K. Chauhan on Mar 31, 2024

A string s is given, the task is to print all subsequences of s using recursion. Every string of size n will have 2^n subsequences.

Example 1: Print subsequences of "abc".

Input: "abc"
Output:


c
b
bc
a
ac
ab
abc

Example 2: Print subsequences of "vxyz".

Input: "vxyz"
Output:


z
y
yz
x
xz
xy
xyz
v
vz
vy
vyz
vx
vxz
vxy
vxyz


Solutions

Method 1: Recursion

As the pattern shows - to obtain any subsequence we are either choosing a character or dropping a character. This is exactly, what we need to do here, we will run the fn recursively twice, once including the current value in subsequence and other without including the current value in subsequence.

As soon as the iteration is complete we will print the subsequence.

package com.cb.recursion;

public class R11_SubSequence {

    public static void printSubSequence(String s, int index, String subString) {
        if (index >= s.length()) {
            System.out.println(subString);
            return;
        }

        // not taking current character
        printSubSequence(s, index + 1, subString);

        // taking current character
        subString += s.charAt(index);
        printSubSequence(s, index + 1, subString);
    }

    public static void main(String[] args) {
        printSubSequence("abc", 0, "");
    }
}


c
b
bc
a
ac
ab
abc

Complexity

For every element two recursive case originates, so Time Complexity is O(2^n). For each character we need to store values in two strings (subsequence), so Space Complexity is O(2^n).

Related


Find all substrings of a string in "O (n^2)" time

Reverse words in a given string

Swap all occurrences of two characters to get lexicographically smallest string

Check if two given strings are isomorphic to each other

Print all permutations of a given string

Longest Common Prefix in an Array of Strings

Check if two strings are equal or not after processing backspace

Transform One String to Another with a Minimum Number of Operations

Check whether the given string is a palindrome

Power Set: Print all non-empty subsequences of a string