有重复字符串的排列组合

1
2

 输入：S = "qqe"
 输出：["eqq","qeq","qqe"]

1
2

 输入：S = "ab"
 输出：["ab", "ba"]

 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
34
35
36
37
38
39
40
41

func permutation(S string) []string {

    var a = []byte(S)
    sort.Slice(a,func(i,j int) bool {
        return a[i] < a[j]
    })
    var n = len(a)
    var res []string
    var path []byte
    var visited = make([]bool,n)
    //排序完成
    var dfs func()
    
    dfs = func() {
        if len(path) == n {
            res = append(res,string(path))
            return
        }
        for i,_ := range a {
            if visited[i] == false {
                /*
                    解释 ，设 x = a[i], 那么 x也等于 a[i-1]
                    如果上一个 x 没有用到，那么这个 x也不能使用
                    必须要 上一个 相邻的x使用了，这个 x才能使用，我们需要按序使用 x 才不会出现重复的排列
                    如果上个 x 没有用，这轮用了这个 x,那么 下一次，一定会生成两个重复的 序列
                */
                //没有访问过
                if i> 0 && a[i] == a[i-1] && visited[i-1]== false {
                    continue
                }
                path = append(path, a[i])
                visited[i] = true
                dfs()
                visited[i] = false
                path = path[:len(path)-1]
            }
        }
    }
    dfs()
    return res
}