All Permutations II

Given a string with possible duplicate characters, return a list with all permutations of the characters.

Examples

• Set = “abc”, all permutations are [“abc”, “acb”, “bac”, “bca”, “cab”, “cba”]

• Set = "aba", all permutations are ["aab", "aba", "baa"]

• Set = "", all permutations are [""]

• Set = null, all permutations are []

Solution: Recursive DFS with Hashset

public class Solution {
  public List<String> permutations(String input) {
    if (input == null) return new ArrayList<String>();
    if (input.length() == 0) {
      List<String> empty = new ArrayList<>();
      empty.add("");
      return empty;
    }
    //sanity check
    
    List<String> result = new ArrayList<String>();
    char[] array = input.toCharArray();

    helper(result, array, 0);
    return result;
  }

  public void helper(List<String> result, char[] array, int index){
    if (index == array.length){
      result.add(new String(array));
      return;
    }

    Set<Character> used = new HashSet<>();
    for (int i = index; i < array.length; i++){
      if (used.contains(array[i])){
        continue;
      }
      used.add(array[i]);
      swap(array, index, i);
      helper(result, array, index + 1);
      swap(array, index, i);
    }
  }

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

Time Comp: O(N) Hashset * O(N!) branches = O(N^2)

Space Comp: O(N) Hashset