public class Solution {
  // approach: DFS
  // time complexity: O(n!)
  // space complexity: O(n)
  public List<String> permutations(String set) {
    List<String> result = new ArrayList<>();
    if (set == null) {
      return result;
    }
    char[] array = set.toCharArray();
    helper(array, result, 0);
    return result;
  }
  private void helper(char[] array, List<String> result, int index) {
    // base case
    if (index >= array.length - 1) {
      result.add(new String(array));
      return;
    }

    for (int i = index; i < array.length; i++) {
      swap(array, i, index);
      helper(array, result, index + 1);
      swap(array, i, index);
    }
  }
  private void swap(char[] array, int i, int j) {
    char temp = array[i];
    array[i] = array[j];
    array[j] = temp;
  }
}