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 [].

Solution: DFS

Each layer one index

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

Perform permutation with:

swap swap

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!)

SC:

Heap: O(N!) result array

Stack: O(N)