Problem

Given a string s that may contain duplicate characters, return all unique permutations of s (order does not matter).

Examples

Example 1

1
2
3

Input: s = "abc"
Output: ["abc","acb","bac","bca","cab","cba"]
Explanation: 3! = 6 unique permutations.

Example 2

1
2
3

Input: s = "aba"
Output: ["aab","aba","baa"]
Explanation: Duplicates reduce the number of unique permutations.

Example 3

1
2

Input: s = "ABCA"
Output: ["AABC","AACB","ABAC","ABCA","ACBA","ACAB","BAAC","BACA","BCAA","CABA","CAAB","CBAA"]
Similar Problems

Solution

We present two common approaches: (1) sort-and-skip duplicates while backtracking, and (2) backtracking using a frequency (count) map. Both generate exactly the set of unique permutations; the second avoids duplicate branches explicitly and is often cleaner.

Method 1 — Sort-and-skip backtracking

Intuition

Sort the characters so equal characters are adjacent. During backtracking, when deciding which character to place at the current position, skip a character if it is the same as a previous character that has not been used at this recursion level — that ensures we don’t generate the same permutation multiple times.

Approach

  • Sort s into a char array arr.
  • Maintain a boolean used[] of the same length to mark which positions are already placed.
  • Recursively build the current permutation cur:
    • If i == n, add cur to ans.
    • Otherwise, iterate j from 0 to n-1:
      • If used[j] is true, skip.
      • If j > 0 and arr[j] == arr[j-1] and !used[j-1], skip (this removes duplicate branches).
      • Mark used[j] = true, append arr[j], recurse, then undo.

This generates each unique permutation exactly once.

Code

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31

class Solution {
public:
  vector<string> permuteUnique(string s) {
    int n = s.size();
    vector<string> ans;
    if (n == 0) return ans;
    sort(s.begin(), s.end());
    string cur; cur.reserve(n);
    vector<bool> used(n, false);
    dfs(s, used, cur, ans);
    return ans;
  }

private:
  void dfs(const string &s, vector<bool> &used, string &cur, vector<string> &ans) {
    int n = s.size();
    if ((int)cur.size() == n) {
      ans.push_back(cur);
      return;
    }
    for (int i = 0; i < n; ++i) {
      if (used[i]) continue;
      if (i > 0 && s[i] == s[i-1] && !used[i-1]) continue;
      used[i] = true;
      cur.push_back(s[i]);
      dfs(s, used, cur, ans);
      cur.pop_back();
      used[i] = false;
    }
  }
};
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33

package main

import "sort"

type Solution struct{}

func (Solution) Permute(s string) []string {
  n := len(s)
  if n == 0 { return []string{} }
  arr := []byte(s)
  sort.Slice(arr, func(i, j int) bool { return arr[i] < arr[j] })
  used := make([]bool, n)
  var ans []string
  var cur []byte
  var dfs func()
  dfs = func() {
    if len(cur) == n {
      ans = append(ans, string(append([]byte(nil), cur...)))
      return
    }
    for i := 0; i < n; i++ {
      if used[i] { continue }
      if i > 0 && arr[i] == arr[i-1] && !used[i-1] { continue }
      used[i] = true
      cur = append(cur, arr[i])
      dfs()
      cur = cur[:len(cur)-1]
      used[i] = false
    }
  }
  dfs()
  return ans
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30

import java.util.*;

class Solution {
  public List<String> permute(String s) {
    List<String> ans = new ArrayList<>();
    if (s == null || s.length() == 0) return ans;
    char[] arr = s.toCharArray();
    Arrays.sort(arr);
    boolean[] used = new boolean[arr.length];
    StringBuilder cur = new StringBuilder();
    dfs(arr, used, cur, ans);
    return ans;
  }

  private void dfs(char[] arr, boolean[] used, StringBuilder cur, List<String> ans) {
    if (cur.length() == arr.length) {
      ans.add(cur.toString());
      return;
    }
    for (int i = 0; i < arr.length; i++) {
      if (used[i]) continue;
      if (i > 0 && arr[i] == arr[i-1] && !used[i-1]) continue;
      used[i] = true;
      cur.append(arr[i]);
      dfs(arr, used, cur, ans);
      cur.deleteCharAt(cur.length() - 1);
      used[i] = false;
    }
  }
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22

class Solution {
  fun permute(s: String): List<String> {
    val arr = s.toCharArray().apply { sort() }
    val ans = mutableListOf<String>()
    val used = BooleanArray(arr.size)
    val cur = StringBuilder()
    fun dfs() {
      if (cur.length == arr.size) { ans.add(cur.toString()); return }
      for (i in arr.indices) {
        if (used[i]) continue
        if (i > 0 && arr[i] == arr[i-1] && !used[i-1]) continue
        used[i] = true
        cur.append(arr[i])
        dfs()
        cur.deleteCharAt(cur.length - 1)
        used[i] = false
      }
    }
    dfs()
    return ans
  }
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26

class Solution:
  def permute(self, s: str) -> list[str]:
    n = len(s)
    if n == 0:
      return []
    arr = sorted(s)
    used = [False] * n
    ans: list[str] = []

    def dfs(cur: list[str]) -> None:
      if len(cur) == n:
        ans.append(''.join(cur))
        return
      for i in range(n):
        if used[i]:
          continue
        if i > 0 and arr[i] == arr[i-1] and not used[i-1]:
          continue
        used[i] = True
        cur.append(arr[i])
        dfs(cur)
        cur.pop()
        used[i] = False

    dfs([])
    return ans
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30

pub struct Solution;
impl Solution {
  pub fn permute(s: String) -> Vec<String> {
    let mut arr: Vec<char> = s.chars().collect();
    arr.sort();
    let n = arr.len();
    let mut used = vec![false; n];
    let mut ans = Vec::new();
    let mut cur = Vec::with_capacity(n);

    fn dfs(arr: &Vec<char>, used: &mut Vec<bool>, cur: &mut Vec<char>, ans: &mut Vec<String>) {
      if cur.len() == arr.len() {
        ans.push(cur.iter().collect());
        return;
      }
      for i in 0..arr.len() {
        if used[i] { continue }
        if i > 0 && arr[i] == arr[i-1] && !used[i-1] { continue }
        used[i] = true;
        cur.push(arr[i]);
        dfs(arr, used, cur, ans);
        cur.pop();
        used[i] = false;
      }
    }

    dfs(&arr, &mut used, &mut cur, &mut ans);
    ans
  }
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25

export class Solution {
  permute(s: string): string[] {
    const arr = s.split('').sort();
    const n = arr.length;
    const used = new Array<boolean>(n).fill(false);
    const ans: string[] = [];
    const cur: string[] = [];

    function dfs(): void {
      if (cur.length === n) { ans.push(cur.join('')); return; }
      for (let i = 0; i < n; i++) {
        if (used[i]) continue;
        if (i > 0 && arr[i] === arr[i-1] && !used[i-1]) continue;
        used[i] = true;
        cur.push(arr[i]);
        dfs();
        cur.pop();
        used[i] = false;
      }
    }

    dfs();
    return ans;
  }
}

Complexity

  • ⏰ Time complexity: O(n * P) where P is the number of unique permutations (in worst case P = n! for distinct characters). Each permutation is built in O(n) time.
  • 🧺 Space complexity: O(n + P*n) if including output; O(n) auxiliary recursion/used arrays.

Method 2 — Backtracking with frequency map (count-selection)

Intuition

Instead of permuting positions, track counts of each unique character and at each step choose a character with remaining count > 0. This avoids duplicate branches entirely and is efficient when many duplicates exist.

Approach

  • Build a map count from character → remaining count.
  • Recursively append any character c with count[c] > 0, decrement count[c], recurse, then restore count[c].
  • When the current length reaches n, append the current permutation to ans.

This method generates each unique permutation exactly once without explicit duplicate checks.

Code

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26

class Solution2 {
public:
  vector<string> permuteUnique(string s) {
    int n = s.size();
    unordered_map<char,int> cnt;
    for (char c : s) ++cnt[c];
    vector<string> ans;
    string cur; cur.reserve(n);
    dfs(cnt, n, cur, ans);
    return ans;
  }

private:
  void dfs(unordered_map<char,int> &cnt, int n, string &cur, vector<string> &ans) {
    if ((int)cur.size() == n) { ans.push_back(cur); return; }
    for (auto &p : cnt) {
      char c = p.first;
      if (p.second == 0) continue;
      --p.second;
      cur.push_back(c);
      dfs(cnt, n, cur, ans);
      cur.pop_back();
      ++p.second;
    }
  }
};
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23

class Solution2:
    def permuteUnique(self, s: str) -> list[str]:
        n = len(s)
        from collections import Counter
        cnt = Counter(s)
        ans: list[str] = []
        cur: list[str] = []

        def dfs() -> None:
            if len(cur) == n:
                ans.append(''.join(cur))
                return
            for c in list(cnt.keys()):
                if cnt[c] == 0:
                    continue
                cnt[c] -= 1
                cur.append(c)
                dfs()
                cur.pop()
                cnt[c] += 1

        dfs()
        return ans

Complexity

  • ⏰ Time complexity: O(n * P) where P is number of unique permutations; this method avoids duplicate recursion branches, so it’s often faster in practice when duplicates exist.
  • 🧺 Space complexity: O(n + P*n) including output; O(k + n) auxiliary where k is number of distinct characters for the count map.