第一种思路是使用 Next Permutation 中的思路，不断迭代，求下一个全排列即可，需要注意的是，一个序列全排列的个数是 n!个。
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
| import "sort"
func permute(nums []int) [][]int {
n:=len(nums)
if n<=1 {
return [][]int{nums}
}
retLen:=1
for i:=n;i>=2;i-- {
retLen*=i
}
ret:=make([][]int,retLen)
t:=make([]int,n)
copy(t,nums)
ret[0]=t
for i:=1;i<retLen;i++ {
j:=n-2
k:=n-1
for j>=0 && nums[j]>=nums[j+1]{
j--
}
if j>=0{
for nums[k]<=nums[j]{
k--
}
nums[j],nums[k]=nums[k],nums[j]
}
sort.Ints(nums[j+1:])
t:=make([]int,n)
copy(t,nums)
ret[i]=t
}
return ret
}
|
另一种思路是使用回溯递归，将每一种情况使用递归的方式加入进去。
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
| func backtracking(ret *[][]int, nums[]int, now []int){
if len(nums)==len(now) {
t:=make([]int,len(nums))
copy(t,now)
*ret=append(*ret,t)
return
}
for _,n:=range nums {
needContinue:=false
for _,t:=range now{
if t==n {
needContinue=true
break
}
}
if !needContinue {
now=append(now,n)
backtracking(ret,nums,now)
now=now[:len(now)-1]
}
}
}
func permute(nums []int) [][]int {
ret:=[][]int{}
backtracking(&ret,nums,[]int{})
return ret
}
|