> 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/subsets-of-all-permuations.md).

# Subsets of all permuations

Medium

Given a string with no duplicate characters, return a list with all permutations of the string and all its subsets.

Examples

Set = “abc”, all permutations are \[“”, “a”, “ab”, “abc”, “ac”, “acb”, “b”, “ba”, “bac”, “bc”, “bca”, “c”, “cb”, “cba”, “ca”, “cab”].

Set = “”, all permutations are \[“”].

Set = null, all permutations are \[].<br>

**Solution:** DFS&#x20;

Each layer one index

Each layer represents Permutation(n choose index + 1) \*zero index

Perform permutation with:

swap swap

```java
public class Solution {
  public List<String> allPermutationsOfSubsets(String set) {
    List<String> result = new ArrayList<>();
    helper(set.toCharArray(), 0, result);
    return result;
  }

  public void helper(char[] arr, int index, List<String> result) {
    result.add(new String(arr, 0 , index));

    for (int i = index; i < arr.length; i++) {
      swap(arr,index, i);
      helper(arr, index+1, result);
      swap(arr, index, i); // revert
    }
  }

  public void swap(char[] arr, int i, int j) {
    char temp = arr[i];
    arr[i] = arr[j];
    arr[j] = temp;
  }
}

```

TC: O(N!)&#x20;

SC:&#x20;

Heap: O(N!) result array&#x20;

Stack: O(N)