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.