无重复字符串的排列组合。编写一种方法，计算某字符串的所有排列组合，字符串每个字符均不相同。
示例1:
输入：S = “qwe”
输出：[“qwe”, “qew”, “wqe”, “weq”, “ewq”, “eqw”]
示例2:
输入：S = “ab”
输出：[“ab”, “ba”]
提示:
字符都是英文字母。
字符串长度在[1, 9]之间。
法一：递归，每次处理一个下标的元素，同时把当时已经选择的内容记录下来防止重复选取：
func permutation(S string) []string {
ans := []string{}
oneAns := make([]byte, len(S))
choosedIdx := 0
findAns(&S, oneAns, 0, &ans, choosedIdx)
return ans
}
func findAns(S *string, oneAns []byte, curIdx int, ans *[]string, choosedIdx int) {
if curIdx == len(*S) {
*ans = append(*ans, string(oneAns))
return
}
for i := 0; i < len(*S); i++ {
if (choosedIdx & (1 << i)) != 0 {
continue
}
oneAns[curIdx] = (*S)[i]
choosedIdx |= 1 << i
findAns(S, oneAns, curIdx+1, ans, choosedIdx)
choosedIdx &= ^(1 << i)
}
}
法二：交换法，如字符串abc，我们先把它加入到结果集。第一轮遍历，我们把结果集中每个字符串（当前只有一个字符串abc）的第一个字符与后面的每个字符交换，交换的结果加入结果集，第一次遍历后，结果集为abc、bac、cba；第二轮遍历，我们把结果集中每个字符串的第二个字符与后面的每个字符交换，交换的结果加入结果集，第二次遍历后，结果集为abc、bac、cba（到此是上次遍历的结果集内容）、acb、bca、cab。
func permutation(S string) []string {
ans := []string{S}
for i := 0; i < len(S)-1; i++ {
curSize := len(ans)
for j := i + 1; j < len(S); j++ {
for k := 0; k < curSize; k++ {
oneAns := []byte(ans[k])
oneAns[i], oneAns[j] = oneAns[j], oneAns[i]
ans = append(ans, string(oneAns))
}
}
}
return ans
}