[Amazon] All Strings by Placing Spaces

Question

link

Given a string, print all possible strings that can be made by placing spaces (zero or one) in between them.

Input: str[] = “ABC”

Output:

    ABC
    AB C
    A BC
    A B C

Solution

recursion.

Code

public void printAll(String input) {
    if (input == null || input.length() <= 1) {
        // since we insert space in-between chars, so
        return;
    }
    int len = input.length();
    // len >= 2
    helper(input, len - 1);
}

private void helper(String s, int p) {
    if (p == 1) {
        System.out.println(s);
        // no insertion
        System.out.println(s.substring(0, 1) + " " + s.substring(1));
        // insert at position 1
    } else {
        helper(s, p - 1);
        helper(s.substring(0, p) + " " + s.substring(p), p - 1);
    }
}