Home » Interview coding problems/challenges

# Print all subsequences of a string

Here, we are going to learn about the solution of print all subsequences of a string using Backtracking algorithm and its C++ implementation.

Submitted by Divyansh Jaipuriyar, on August 20, 2020

**Problem statement:**

You are given a string, you have to print all the subsequences of the string in lexicographical order.

**Problem description:**

The above problem wants you to print all possible arrangement of the string, that is using string length 1 to maximum valid length and also the string should be in lexicographical order which means according to dictionary appearance or sorted sequence.

**Input:**

The first line of the input consist of *T* number of test cases, each test case consist of a string *str*.

**Output:**

You need to print all the subsequences of the given string int lexicographical order separated by new line.

**Examples:**

Input: T=1 str="aa" Output: a a aa Input: T=1 str="abc" Output: a ab abc ac b bc c

**Solution approach:**

To solve this problem we will use the backtracking concept along with multiset which will store the subsequences in lexicographical order.

For each character in the given string, it has two options either it will be in the subsequence or will not be in the subsequence, because for this reason, we need to backtrack the solution.

**Pseudo Code:**

- We declare a solve function.
- It takes two parameters as a string (
*str*) and position (*pos*). - The
*pos*will be the index from where we will start the insertion of character in temporary string*temp*. - Then we will again call solve function and add 1 to current index and recursively move forward.
- Once we reached the maximum index in recursive calls we will backtrack the current index from where recursion started and pop the character which was inserted in temp string initially.
- During each call of the solve function, we will insert the temporary string in the multiset.

**Time Complexity** for the above approach in the worst case is **exponential**.

**C++ Implementation:**

#include <bits/stdc++.h> using namespace std; typedef long long ll; //temporary string. string temp; //multiset for maintaining //lexicographical order. multiset<string> st; //solve function which will make //recursive calls void solve(string str, ll pos) { //insert in multiset. st.insert(temp); //iterate through all characters. for (ll i = pos; i < str.length(); i++) { //insert current character. temp.push_back(str[i]); //make recursive call. solve(str, i + 1); //backtrack temp.pop_back(); } } int main() { cout << "Enter number of test cases: "; int t; cin >> t; while (t--) { st.clear(); cout << "Enter string: "; string str; cin >> str; temp = ""; solve(str, 0); cout << "Possible Subsequences in lexicographical order:"; for (auto it = st.begin(); it != st.end(); it++) cout << *it << "\n"; } return 0; }

**Output:**

Enter number of test cases: 3 Enter string: ab Possible Subsequences in lexicographical order: a ab b Enter string: abc Possible Subsequences in lexicographical order: a ab abc ac b bc c Enter string: aa Possible Subsequences in lexicographical order: a a aa

TOP Interview Coding Problems/Challenges

- Run-length encoding (find/print frequency of letters in a string)
- Sort an array of 0's, 1's and 2's in linear time complexity
- Checking Anagrams (check whether two string is anagrams or not)
- Relative sorting algorithm
- Finding subarray with given sum
- Find the level in a binary tree with given sum K
- Check whether a Binary Tree is BST (Binary Search Tree) or not
- 1[0]1 Pattern Count
- Capitalize first and last letter of each word in a line
- Print vertical sum of a binary tree
- Print Boundary Sum of a Binary Tree
- Reverse a single linked list
- Greedy Strategy to solve major algorithm problems
- Job sequencing problem
- Root to leaf Path Sum
- Exit Point in a Matrix
- Find length of loop in a linked list
- Toppers of Class
- Print All Nodes that don't have Sibling
- Transform to Sum Tree
- Shortest Source to Destination Path

Comments and Discussions