# 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


---

# Agent Instructions: Querying This Documentation

If you need additional information that is not directly available in this page, you can query the documentation dynamically by asking a question.

Perform an HTTP GET request on the current page URL with the `ask` query parameter:

```
GET https://llssff.gitbook.io/coding-problems/dfs-permutations/all-subsets-i.md?ask=<question>
```

The question should be specific, self-contained, and written in natural language.
The response will contain a direct answer to the question and relevant excerpts and sources from the documentation.

Use this mechanism when the answer is not explicitly present in the current page, you need clarification or additional context, or you want to retrieve related documentation sections.