> For the complete documentation index, see [llms.txt](https://llssff.gitbook.io/coding-problems/llms.txt). Markdown versions of documentation pages are available by appending `.md` to page URLs; this page is available as [Markdown](https://llssff.gitbook.io/coding-problems/dfs-permutations/all-subsets-i.md).

# 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