46. 全排列
给定一个不含重复数字的数组 nums ，返回其 所有可能的全排列 。你可以 按任意顺序 返回答案。
示例 1：
输入：nums = [1,2,3]
输出：[[1,2,3],[1,3,2],[2,1,3],[2,3,1],[3,1,2],[3,2,1]]
示例 2：输入：nums = [0,1]
输出：[[0,1],[1,0]]
示例 3：输入：nums = [1]
输出：[[1]]
回溯+used数组
var ans [][]int
var list []int
func permute(nums []int) [][]int {
ans = make([][]int, 0)
list = make([]int, 0)
used := make([]bool, len(nums))
backTrack(nums, used)
return ans
}
func backTrack(nums []int, used []bool) {
if len(list) == len(nums) {
tmp := make([]int, len(nums))
copy(tmp, list)
ans = append(ans, tmp)
return
}
for i := 0; i < len(nums); i ++ {
if !used[i] {
used[i] = true
list = append(list, nums[i])
backTrack(nums, used)
list = list[:len(list)-1]
used[i] = false
}
}
}
47. 全排列 II
给定一个可包含重复数字的序列 nums ，按任意顺序 返回所有不重复的全排列。
示例 1：
输入：nums = [1,1,2]
输出：
[[1,1,2],
[1,2,1],
[2,1,1]]
示例 2：输入：nums = [1,2,3]
输出：[[1,2,3],[1,3,2],[2,1,3],[2,3,1],[3,1,2],[3,2,1]]提示：
1 <= nums.length <= 8
-10 <= nums[i] <= 10
回溯+used数组+set去重
var ans [][]int
var list []int
func permuteUnique(nums []int) [][]int {
ans = make([][]int, 0)
list = make([]int, 0)
used := make([]bool, len(nums))
backTrack(nums, used)
return ans
}
func backTrack(nums []int, used []bool) {
if len(list) == len(nums) {
tmp := make([]int, len(nums))
copy(tmp, list)
ans = append(ans, tmp)
return
}
set := make(map[int]bool)
for i := 0; i < len(nums); i ++ {
if !used[i] && !set[nums[i]]{
used[i] = true
list = append(list, nums[i])
set[nums[i]] = true
backTrack(nums, used)
used[i] = false
list = list[:len(list)-1]
}
}
}
