题解 | #字符串的排列#

package main

import (
	"sort"
	"strings"
)

/**
 * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
 *
 *
 * @param str string字符串
 * @return string字符串一维数组
 */
func Permutation(str string) []string {
	// write code here
	var ret []string
	if len(str) == 0 {
		return ret
	}

	arr := strings.Split(str, "")
	// 排序后重复的字符就会相邻
	sort.Strings(arr)
	// 用于组装临时字符串
	var tmp []string
	// 标记每个位置的字符是否被使用过
	visited := make([]bool, len(arr))
	var backtrack func(arr []string, tmp []string, visited []bool)
	backtrack = func(arr []string, tmp []string, visited []bool) {
		if len(tmp) == len(arr) {
			ret = append(ret, strings.Join(tmp, ""))

			return
		}

		// 遍历所有元素选取一个加入
		for i := 0; i < len(arr); i++ {
			// 该元素已经被加入了
			if visited[i] {
				continue
			}

			// 重复的字符使用过了
			if i > 0 && arr[i] == arr[i-1] && visited[i-1] {
				continue
			}

			visited[i] = true

			tmp = append(tmp, arr[i])
			backtrack(arr, tmp, visited)

			// 回溯
			visited[i] = false
			tmp = tmp[:len(tmp)-1]
		}
	}
	backtrack(arr, tmp, visited)

	return ret
}