LogoKode$word
All Subsequences of a String (Power Set) | Recursion & Backtracking Java Solution
All Subsequences of a String (Power Set) | Recursion & Backtracking Java Solution

All Subsequences of a String (Power Set) | Recursion & Backtracking Java Solution

Learn how to generate all subsequences of a string using recursion, backtracking, and bit manipulation. Includes Java code and lexicographical sorting.

4 views
0
0
Github icon
Listen to articleAudio version

Introduction

The Power Set problem for strings is a classic question in recursion and backtracking, frequently asked in coding interviews and platforms like GeeksforGeeks.

In this problem, instead of numbers, we deal with strings and generate all possible subsequences (not substrings). This makes it slightly more interesting and practical for real-world applications like pattern matching, text processing, and combinatorics.

In this article, we will cover:

  1. Intuition behind subsequences
  2. Recursive (backtracking) approach
  3. Sorting for lexicographical order
  4. Alternative approaches
  5. Complexity analysis

Problem Statement

Given a string s of length n, generate all non-empty subsequences of the string.

Requirements

  1. Return only non-empty subsequences
  2. Output must be in lexicographically sorted order

Examples

Example 1

Input:

s = "abc"

Output:

a ab abc ac b bc c

Example 2

Input:

s = "aa"

Output:

a a aa

Subsequence vs Substring (Important)

  1. Substring: Continuous characters
  2. Subsequence: Characters can be skipped

Example for "abc":

Subsequences → a, b, c, ab, ac, bc, abc

Key Insight

For every character, we have two choices:

Include it OR Exclude it

So total subsequences:

2^n

We generate all and then remove the empty string.

Approach 1: Recursion (Backtracking)

Intuition

  1. At each index:
  2. Skip the character
  3. Include the character
  4. Build all combinations recursively

Java Code (With Explanation)

import java.util.*;

class Solution {

// List to store all subsequences
List<String> a = new ArrayList<>();

void sub(String s, int ind, String curr) {

// Base case: reached end of string
if (ind == s.length()) {
a.add(curr); // add current subsequence
return;
}

// Choice 1: Exclude current character
sub(s, ind + 1, curr);

// Choice 2: Include current character
sub(s, ind + 1, curr + s.charAt(ind));
}

public List<String> AllPossibleStrings(String s) {

// Start recursion
sub(s, 0, "");

// Remove empty string (not allowed)
a.remove("");

// Sort lexicographically
Collections.sort(a);

return a;
}
}

Step-by-Step Dry Run (s = "abc")

Start: ""

→ Exclude 'a' → ""
→ Exclude 'b' → ""
→ Exclude 'c' → ""
→ Include 'c' → "c"

→ Include 'b' → "b"
→ Exclude 'c' → "b"
→ Include 'c' → "bc"

→ Include 'a' → "a"
→ Exclude 'b' → "a"
→ Exclude 'c' → "a"
→ Include 'c' → "ac"

→ Include 'b' → "ab"
→ Exclude 'c' → "ab"
→ Include 'c' → "abc"

Final Output (After Sorting)

a ab abc ac b bc c

Approach 2: Bit Manipulation

Intuition

Each subsequence can be represented using binary numbers:

0 → exclude
1 → include

Code

import java.util.*;

class Solution {
public List<String> AllPossibleStrings(String s) {
List<String> result = new ArrayList<>();
int n = s.length();

int total = 1 << n; // 2^n

for (int i = 1; i < total; i++) { // start from 1 to avoid empty
StringBuilder sb = new StringBuilder();

for (int j = 0; j < n; j++) {
if ((i & (1 << j)) != 0) {
sb.append(s.charAt(j));
}
}

result.add(sb.toString());
}

Collections.sort(result);
return result;
}
}

Approach 3: Iterative (Expanding List)

Idea

  1. Start with empty list
  2. For each character:
  3. Add it to all existing subsequences

Code

import java.util.*;

class Solution {
public List<String> AllPossibleStrings(String s) {
List<String> result = new ArrayList<>();
result.add("");

for (char ch : s.toCharArray()) {
int size = result.size();

for (int i = 0; i < size; i++) {
result.add(result.get(i) + ch);
}
}

result.remove("");
Collections.sort(result);
return result;
}
}

Complexity Analysis

  1. Time Complexity: O(n × 2ⁿ)
  2. Space Complexity: O(n × 2ⁿ)

Why?

  1. Total subsequences = 2ⁿ
  2. Each subsequence takes O(n) to build

Why Sorting is Required

The recursion generates subsequences in random order, so we sort them:

Collections.sort(result);

This ensures lexicographical order as required.

Key Takeaways

  1. This is a power set problem for strings
  2. Each character → 2 choices
  3. Recursion = most intuitive approach
  4. Bit manipulation = most optimized thinking
  5. Always remove empty string if required

Common Interview Variations

  1. Subsets of array
  2. Permutations of string
  3. Combination sum
  4. Subsequence with conditions

Conclusion

The Power Set problem is a fundamental building block in recursion and combinatorics. Once you understand the include/exclude pattern, you can solve a wide range of problems efficiently.

Mastering this will significantly improve your ability to tackle backtracking and decision tree problems.

Frequently Asked Questions (FAQs)

1. Why is the empty string removed?

Because the problem requires only non-empty subsequences.

2. Why is time complexity O(n × 2ⁿ)?

Because there are 2ⁿ subsequences and each takes O(n) time to construct.

3. Which approach is best?

  1. Recursion → best for understanding
  2. Bit manipulation → best for optimization

Related Articles

LeetCode 1021: Remove Outermost Parentheses — Java Solution Explained

LeetCode 1021: Remove Outermost Parentheses — Java Solution Explained

Learn How to Identify and Remove Outermost Parentheses of Every Primitive Component Using Counter and Stack Approaches in Java — With Full Dry Run and Complexity Analysis

Read Article
LeetCode 187 – Repeated DNA Sequences (Java Solution with Sliding Window and HashSet)

LeetCode 187 – Repeated DNA Sequences (Java Solution with Sliding Window and HashSet)

Step-by-Step Explanation with Optimized Approach and Time Complexity Analysis

Read Article
Longest Substring with K Unique Characters – Efficient Sliding Window Solution

Longest Substring with K Unique Characters – Efficient Sliding Window Solution

Master the sliding window technique using HashMap to find the longest substring with exactly K distinct characters.

Read Article
Longest Repeating Character Replacement – Sliding Window Explained (LeetCode 424)

Longest Repeating Character Replacement – Sliding Window Explained (LeetCode 424)

Mastering the Sliding Window Pattern with Frequency Optimization

Read Article
Ai Assistant Kas
All Subsequences of a String (Power Set) | Recursion & Backtracking Java Solution | Kode$word