剑指 Offer 38. 字符串的排列

https://leetcode-cn.com/problems/zi-fu-chuan-de-pai-lie-lcof/

可以用经典回溯法生成全排列，但是要注意一个问题：如果给定输入字符串中有重复字符，会生成重复的排列。

因此在决定填入某个字符时，如果这个字符在这个位置上已经用过一次了，就不能再用了。用一个哈希表记录已经填过的字符。

var res []string
var used []bool   // 记录哪些字符已被使用 
var track string

func permutation(s string) []string {
    res = make([]string, 0)
    used = make([]bool, len(s))
    backtrack(s)
    return res
}

func backtrack(s string) {
    if len(track) == len(s) {
        res = append(res, track)       
    }

    // 在填入此位置时，不能使用重复字符
    set := make(map[rune]bool)

    // 尝试填入所有可能的字符
    for i, r := range s {
        // 如果当前字符已被使用，或是已经填过了一样的字符，都直接跳过
        if _, ok := set[r]; ok || used[i] == true {
            continue
        }
        set[r] = true

        used[i] = true
        track += string(r)
        backtrack(s)
        used[i] = false
        track = track[:len(track)-1]
    }
}