题解 | #字符串的排列#回溯

package main
// import "fmt"
import "sort"
/**
 * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
 *
 * 
 * @param str string字符串 
 * @return string字符串一维数组
*/
func Permutation( str string ) []string {
    // write code here
    n:=len(str)
    if n==0{
        return []string{}
    }
    //按字典序排序，可以实现结果集去重
    s := []byte(str)
    sort.Slice(s, func(i,j int)bool{
        return s[i]<s[j]
    })
    ans := []string{}
    used := make([]bool, n)
//     has_in := make(map[string]int) //标记字符串，用于结果集去重
    path := []byte{}
    var backtrack func(s []byte, used []bool, path []byte)
    backtrack = func(s []byte, used []bool, path []byte){
        if len(path)==n{
//             if _,ok := has_in[string(path)]; !ok{
//                 ans = append(ans, string(path))
//                 has_in[string(path)] = 1
//             }
            ans = append(ans, string(path))
            return
        }
        for i:=0;i<n;i++{
            if used[i]{
                continue
            }
            if i>0 && s[i]==s[i-1] && !used[i-1]{
                continue
            }
            used[i] = true
            path = append(path, s[i])
            backtrack(s, used, path)
            used[i] = false
            path = path[:len(path)-1]
        }
    }
    backtrack(s, used, path)
//     fmt.Println(ans)
    return ans
}