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

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

Given a string "s", the task is to find out all non-empty subsequences of it.

A subsequence of a string is a sequence that can be derived from the given string by deleting zero or more elements without changing the order of the remaining elements.

Input: abc 
Output: abc, bc, ac, c, ab, b, a

Input : abcd
Output : abcd, bcd, acd, cd, abd, bd, ad, d, abc, bc, ac, c, ab, b, a

Note: For a string of length n, there are a total of 2^n subsequences. Example: "abc" has 2^3 = 8 sub sequences i.e., "abc", "bc", "ac", "c", "ab ", "b", "a", "".


Solutions

Method 1: Using recursion(Backtracking)

This recursive solution is based on the "Pick and Don't Pick Concept".

Begin with the last element and make two calls in each recursion, one while including the current character in the "subsequence (ss)" and one without.

As soon as the input string is exhausted, print "subsequence (ss)" and return.

Complexity

The time complexity of the above recursive solution is exponential (2^n).

In addition, O(n) auxiliary stack space was used for the recursion stack.

Related


Swap all occurrences of two characters to get lexicographically smallest string

Reverse words in a given string

Print all permutations of a given string

Check whether the given string is a palindrome

Check if two strings are equal or not after processing backspace

Longest Common Prefix in an Array of Strings

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

Print all subsequences of a string

Check if two given strings are isomorphic to each other

Transform One String to Another with a Minimum Number of Operations