> 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/all-permutations-ii.md).

# 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