LogoKode$word
Permutation with Spaces Explained Using Recursion & Decision Tree | Java Solution GFG
Permutation with Spaces Explained Using Recursion & Decision Tree | Java Solution GFG

Permutation with Spaces Explained Using Recursion & Decision Tree | Java Solution GFG

Master the Permutation with Spaces problem using recursion and decision trees. Includes Java code with comments and step-by-step explanation.

15 views
0
0
Github icon
Listen to articleAudio version

Introduction

The Permutation with Spaces problem is a classic recursion question that helps build a strong understanding of decision-making and backtracking patterns.

Instead of generating permutations by rearranging characters, this problem focuses on inserting spaces between characters in all possible ways.

What makes this problem powerful is its decision tree structure, which you’ve already visualized perfectly. In this article, we will directly connect that intuition with code.

Link of Problem: GeeksforGeeks – Permutation with Spaces

Problem Statement

Given a string s, generate all possible strings by placing:

  1. Either a space
  2. Or no space

between every pair of characters.

Return all results in sorted order.

Example

Input:

s = "ABC"

Output:

A B C

A BC

AB C

ABC

Understanding Your Decision Tree (Very Important)

Two Choices at Each Step:

❌ Do NOT add space before the character

✔️ Add space before the character

Mapping Tree

From diagram:

  1. At B:
  2. "AB" → no space
  3. "A B" → space
  4. At C:
  5. From "AB":
  6. "ABC"
  7. "AB C"
  8. From "A B":
  9. "A BC"
  10. "A B C"

Final Output (Leaf Nodes)

As shown in your diagram:

ABC, AB C, A BC, A B C

📌 This is exactly what recursion generates.

Key Insight

At every index (except first), we have:

2 choices → space OR no space

So total combinations:

2^(n-1)

Approach: Recursion + Decision Making

Idea

  1. Fix the first character
  2. For every next character:
  3. Add space + character
  4. Add character directly
  5. Continue recursively

Java Code with Detailed Comments

import java.util.*;

class Solution {
// List to store all results
ArrayList<String> lis = new ArrayList<>();

void solve(String s, int ind, String curr) {
// Base case:
// If index reaches end of string,
// we have formed one valid permutation
if (ind == s.length()) {
lis.add(curr); // store the result
return;
}

// Choice 1: Add SPACE before current character
// Example: "A" → "A B"
solve(s, ind + 1, curr + " " + s.charAt(ind));

// Choice 2: Do NOT add space
// Example: "A" → "AB"
solve(s, ind + 1, curr + s.charAt(ind));
}

ArrayList<String> permutation(String s) {
// Start with first character (no space before it)
String curr = "" + s.charAt(0);

// Start recursion from index 1
solve(s, 1, curr);

// Sort results as required in problem
Collections.sort(lis);

return lis;
}
}

Step-by-Step Execution (Using Your Tree)

For "ABC":

  1. Start → "A"
  2. At "B":
  3. "AB"
  4. "A B"
  5. At "C":
  6. "ABC", "AB C"
  7. "A BC", "A B C"

Exactly matches your decision tree leaf nodes ✅

Complexity Analysis

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

Why This Approach Works

  1. Recursion explores every possible choice
  2. Each level = one character
  3. Each branch = decision (space / no space)
  4. Leaf nodes = final answers

Key Takeaways

  1. This is a binary decision recursion problem
  2. Always identify:
  3. Choices
  4. Base condition
  5. Your decision tree = direct blueprint of recursion
  6. Same pattern applies to:
  7. Subsets
  8. Binary choices problems

Conclusion

The Permutation with Spaces problem becomes extremely simple once the decision tree is understood—and your diagram already captures that perfectly.

The recursion directly follows the same structure:

  1. Every branch = one decision
  2. Every leaf = one answer

Master this pattern, and you’ll find many recursion problems much easier to solve.

Related Articles

Subsets Problem (LeetCode 78) Explained | Recursion, Iterative & Bit Manipulation

Subsets Problem (LeetCode 78) Explained | Recursion, Iterative & Bit Manipulation

Learn how to solve the Subsets problem using recursion, backtracking, loops, and bit manipulation. Includes Java code, intuition, and complexity analysis.

Read Article
Recursion in Java - Complete Guide With Examples and Practice Problems

Recursion in Java - Complete Guide With Examples and Practice Problems

Learn recursion in Java from scratch. Includes how recursion works, base case, recursive case, types of recursion, dry runs, time & space complexity, and top LeetCode problems with solutions.

Read Article
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.

Read Article
Delete Middle Element of Stack Without Extra Space | Java Recursive Solution

Delete Middle Element of Stack Without Extra Space | Java Recursive Solution

Learn how to delete the middle element of a stack without using extra space. Step-by-step explanation with Java code, recursion approach, and examples.

Read Article
Ai Assistant Kas
Permutation with Spaces Explained Using Recursion & Decision Tree | Java Solution GFG | Kode$word