All subsets I

Given a set of characters represented by a String, return a list containing all subsets of the characters.

Assumptions

• There are no duplicate characters in the original set.

​Examples

• Set = "abc", all the subsets are [“”, “a”, “ab”, “abc”, “ac”, “b”, “bc”, “c”]

• Set = "", all the subsets are [""]

• Set = null, all the subsets are []

Solution:

Recursive DFS

Recursion Tree:

                                 _
                            A         _
                        AB     A    B   _
                     ABC  AB AC A BC B C _

Base Case: When Index == set.length; Print current

Recursive rule:

1. Add current letter StringBuilder

2. Recursive call with next letter

3. Delete previous addition to StringBuilder

4. Recursive call with next letter

Implementation:

public void findSubsets(String set){
    if (set == null) return;
    
    StringBuilder sb = new StringBuilder(); //no offense chinese readers
    char[] input = set.toCharArray();
    subsetHelper(input, 0, sb);
}

public void subsetHelper(char[] input, int index, StringBuilder sb){
    if (index == input.length){
        System.out.println(sb);
        return;
    }
    
    //add
    sb.append(input[index]);
    
    //call next element
    subsetHelper(input, index + 1, sb);
    
    //Delete previous
    sb.deleteCharAt(sb.length() - 1);
    
    //Branch right
    subsetHelper(input, index + 1, sb);
}

Time Complexity: O(2^N) , O(2^N * N) if storing result into array

2^N nodes * optional: toString for storing in array

Space Complexity: O(N)

StringBuilder max length = N