全排序一

给定一个没有重复数字的序列，返回其所有可能的全排列。

 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

输入: [1,2,3]
输出:
[
  [1,2,3],
  [1,3,2],
  [2,1,3],
  [2,3,1],
  [3,1,2],
  [3,2,1]
]


思路：
1，2，3
2，1，3
3，2，1

1，2，3
1，3，2

2，1，3
2，3，1

3，2，1
3，1，2

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20

func permute(nums []int) [][]int {
	var res [][]int

	helper2(0, len(nums)-1, nums, &res)

	return res
}

func helper2(left, right int, nums []int, res *[][]int) {
	if left == right {
		*res = append(*res, append([]int{}, nums...))
	} else {
		for i := left; i <= right; i++ {

			nums[i], nums[left] = nums[left], nums[i] //第一个元素总是不变，保证交换后的新序列输出
			helper2(left+1, right, nums, res) 
			nums[i], nums[left] = nums[left], nums[i] //尝试完后回溯
		}
	}
}

全排序二

给定一个可包含重复数字的序列，返回所有不重复的全排列。

[1,1,2] [1] [2,2,4,4] [0,1,0,0,9]

1
2
3
4

[[1,1,2],[1,2,1],[2,1,1]]
[[1]]
[[2,2,4,4],[2,4,2,4],[2,4,4,2],[4,2,2,4],[4,2,4,2],[4,4,2,2]]
[[0,0,0,1,9],[0,0,0,9,1],[0,0,1,0,9],[0,0,1,9,0],[0,0,9,0,1],[0,0,9,1,0],[0,1,0,0,9],[0,1,0,9,0],[0,1,9,0,0],[0,9,0,0,1],[0,9,0,1,0],[0,9,1,0,0],[1,0,0,0,9],[1,0,0,9,0],[1,0,9,0,0],[1,9,0,0,0],[9,0,0,0,1],[9,0,0,1,0],[9,0,1,0,0],[9,1,0,0,0]]

 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

func permuteUnique(nums []int) [][]int {
	var res [][]int
	helper(0, len(nums)-1, nums, &res)
	return res 
}

func helper(left, right int, nums []int, res *[][]int) {
	if left == right {
		*res = append(*res, dump(nums))
	} else {
		visited := map[int]bool{} //没进入一个递归，访问状态归零，因为位置已交换，从交换位置后一位开始
		for i := left; i <= right; i++ {
			if visited[nums[i]] {
				continue
			}
			visited[nums[i]] = true
			nums[i], nums[left] = nums[left], nums[i]
			helper(left+1, right, nums, res)
			nums[i], nums[left] = nums[left], nums[i]
		}
	}
}

func dump(a []int) []int {
	b := make([]int, len(a))
	copy(b, a)
	return b
}