Problem Statement - Given a string you need to print all possible strings that can be made by placing spaces (zero or one) in between them. The output should be printed in sorted increasing order of strings

Problem Link - https://practice.geeksforgeeks.org/problems/permutation-with-spaces3627/1

Recursive tree - At each level, we have a choice either to directly take the character or take it with added space. Also, note that the first char is a default for all the permutations, so we have called the recursive method with output as the first char.

class Solution{
    ArrayList<String> res;    
    ArrayList<String> permutation(String S){
        // Code Here
        res = new ArrayList<>();
        StringBuilder sb = new StringBuilder(S);
        // As all the strings will have first character
        String temp =""; temp = temp + S.charAt(0);
        // Delete this character from stringbuilder and call the recursive method
        sb.deleteCharAt(0);
        helper(sb, temp);
        // To maintain the sorted order
        Collections.reverse(res);
        return res;
    }

    void helper(StringBuilder sb, String output) {
        // If traversed the whole string, we have one output, save it
        if(sb.length()==0)
            {
                res.add(output);
                return;
            }        
        char ch = sb.charAt(0);
        String op1 = output + ch;
        String op2 = output + " " + ch;
        sb.deleteCharAt(0);
        // Below are the two ways to get permutations, either take the char, or take the char with additional space as prefix
        helper(sb, op1);
        helper(sb, op2);
// Add the character back to keep traversing for other inputs
        sb.insert(0, ch);
        return;
    }   
}

Time Complexity - O(2^n) where n is the length of the given strings, as these many levels will be in a recursive tree