Dado um array de números inteiors nums que pode conter elementos duplicados, retorne todas as permutações únicas possíveis em qualquer ordem.

Exemplo:
Entrada: nums = [1,1,2]
Saída: [[1,1,2], [1,2,1], [2,1,1]]

Análise do Algoritmo:
Para tratar duplicatas, o array deve ser ordenado primeiro para agrupar elementos iguais. Utiliza-se backtracking para explorar todas as permutações, e um mapa (ou slice) para rastrear índices usados, evitando repetições no mesmo nível da árvore de recursão. A condição de poda verifica se um elemento igual já foi considerado no mesmo nível, garantindo permutações únicas.

Implementação em Go (versão otiimzada):

func generateUniquePerms(nums []int) [][]int {
    var results [][]int
    var current []int
    length := len(nums)
    if length == 0 {
        return results
    }
    sort.Ints(nums) // Ordenação necessária para detecção de duplicatas
    used := make([]bool, length)
    var backtrack func(int)
    backtrack = func(idx int) {
        if idx == length {
            tmp := make([]int, length)
            copy(tmp, current)
            results = append(results, tmp)
            return
        }
        for i := 0; i < length; i++ {
            if i > 0 && nums[i] == nums[i-1] && !used[i-1] {
                continue // Poda: evita duplicatas no mesmo nível
            }
            if used[i] {
                continue // Elemento já utilizado no caminho atual
            }
            used[i] = true
            current = append(current, nums[i])
            backtrack(idx + 1)
            current = current[:len(current)-1]
            used[i] = false
        }
    }
    backtrack(0)
    return results
}

Implementação Alternativa com Função Separada:

func findUniquePermutations(nums []int) [][]int {
    var result [][]int
    var path []int
    used := make([]bool, len(nums))
    sort.Ints(nums)
    var dfs func()
    dfs = func() {
        if len(path) == len(nums) {
            tmp := make([]int, len(path))
            copy(tmp, path)
            result = append(result, tmp)
            return
        }
        for i := 0; i < len(nums); i++ {
            if i > 0 && nums[i] == nums[i-1] && !used[i-1] {
                continue // Pula elementos duplicados no mesmo nível
            }
            if used[i] {
                continue
            }
            used[i] = true
            path = append(path, nums[i])
            dfs()
            path = path[:len(path)-1]
            used[i] = false
        }
    }
    dfs()
    return result
}

Em ambas as implementações, a ordenação do array e o uso de um slice de booleanos used são cruciais para evitar permutações duplicadas. A poda com base em used[i-1] identifica se o elemento anterior foi desmarcado após backtracking, garantindo que apenas permutações únicas sejam geradas.