前言
猛起更新。
正文
问题来源
今天被人问到全排列含有重复元素。
问题描述
给你一个数组，其中数组中可能有相同值，给出所有全排列。
示例 1:
输入： [1,2,3,2]
输出： [[1 2 3 2] [1 2 2 3] [1 3 2 2] [2 1 3 2] [2 1 2 3] [2 3 1 2] [2 3 2 1] [2 2 3 1] [2 2 1 3] [3 2 1 2] [3 2 2 1] [3 1 2 2]]
分析：
分析：加一个判断能否交换的函数isSwap()，对122，第一个数1与第二个数2交换得到212，然后考虑第一个数1与第三个数2交换，此时由于第三个数等于第二个数，所以第一个数不再与第三个数交换。再考虑212，它的第二个数与第三个数交换可以得到解决221。此时全排列生成完毕。这样我们也得到了在全排列中去掉重复的规则——去重的全排列就是从第一个数字起每个数分别与它后面非重复出现的数字交换。用编程的话描述就是第i个数与第j个数交换时，要求[i,j)中没有与第j个数相等的数。
func dfs(a []int, res *[][]int, t int) {
if t == len(a) {
tmp := make([]int, len(a))
copy(tmp, a)
*res = append(*res,tmp)
}
for i:= t; i < len(a); i++ {
if !isSwap(a, t, i) {
continue
}
a[i], a[t] = a[t], a[i]
dfs(a, res, t+1)
a[i], a[t] = a[t], a[i]
}
}
func permutation(a []int) [][]int {
res := make([][]int,0)
dfs(a, &res, 0)
return res
}
func isSwap(a []int, i, j int) bool {
for k := i; k < j; k++ {
if a[k] == a[j] {
return false
}
}
return true
}
总结：
勤思考。
结语
不管怎么样好好加油。
