两个全排列的题目

第一道题

思路

每次假设我们当前要选择的是index位置的元素，有很多选择，从index开始一直到数组结束
但是我们每次选择之后如何和前面已经选择好的元素组成的数组连接起来呢，我们从后面选择要放置到index位置的元素，与我们目前的index位置的元素进行互换，
之后进行下一层的递归
最后递归回来之后，我们再交换回去

代码


//✅
//核心：如何做到每次从后面的选择，并且不会重复呢？如果后面选择某个元素，我们就把该元素交换到我们已经选择完的下一个元素
//index表示下次从nums中的哪个位置元素开始，因为之前的都已经选好了
func backtrack(ret *[][]int, path []int, index int, nums []int) {
	if len(path) == len(nums) {
		//将当前路径加入到结果中
		temp := make([]int, len(path))
		copy(temp, path)
		*ret = append(*ret, temp)
		return
	}

	//开始进入选择
	for i := index; i < len(nums); i++ {
		//利用交换，让我们每次选择的都放置到上次选择的后面那个相邻元素
		nums[i], nums[index] = nums[index], nums[i]
		//下次我们将index位置的元素加入路径
		path = append(path, nums[index])
		//进入下一层
		backtrack(ret, path, index+1, nums)
		//从路径中撤销
		path = path[:len(path)-1]
		//撤销交换
		nums[i], nums[index] = nums[index], nums[i]
	}
}

func permute(nums []int) [][]int {
	if len(nums) == 0 {
		return nil
	}

	var ret [][]int
	backtrack(&ret, []int{}, 0, nums)
	return ret
}

第二道题

note info 核心：如何避免重复出现。思路：我们使用一个map或者set来统计index位置，我们已经交换过的元素，如果下次要交换的元素与我们之前交换过的元素的元素值相同则跳过，因此我们可以使用map或者set来统计。但是要注意位置，每次递归进来的时候我们都要重新建立针对当前index位置的一个统计容器

思路

每次假设我们当前要选择的是index位置的元素，有很多选择，从index开始一直到数组结束
但是我们每次选择之后如何和前面已经选择好的元素组成的数组连接起来呢，如果放置的元素与我们之前放置过的元素不重复，那么我们将从后面选择要放置到index位置的元素，与我们目前的index位置的元素进行互换，
之后进行下一层的递归
最后递归回来之后，我们再交换回去

代码


//✅
func permuteUnique(nums []int) [][]int {
	if len(nums) == 0 {
		return nil
	}

	var ret [][]int
	backtrack(nums, &ret, 0, []int{})

	return ret
}

func backtrack(nums []int, ret *[][]int, index int, path []int) {
	if len(nums) == len(path) {
		temp := make([]int, len(nums))
		copy(temp, path)
		*ret = append(*ret, temp)
		return
	}

	visited := make(map[int]bool)
	for i := index; i < len(nums); i++ {

		//如果没有被访问过
		if !visited[nums[i]] {
			nums[i], nums[index] = nums[index], nums[i]

			//加入路径以及visited中
			path = append(path, nums[index])
			visited[nums[index]] = true

			//进入到下一层
			backtrack(nums, ret, index+1, path)

			//撤销加入路径以及撤销加入visited中
			path = path[:len(path)-1]

			//❌
			//下面这一行代码是不需要的，因为当前可选的数字如果选了加入到visited下次我们就不可以再选了，所以不可以再撤销了
			//delete(visited, nums[index])

			//撤销交换
			nums[i], nums[index] = nums[index], nums[i]
		}
	}
}