代码随想录day25 || 491 递增子序列，46 全排列， 47 全排列2

491 递增子序列

func findSubsequences(nums []int) [][]int {
	// 思路，在原数组上面找寻递增子序列，所以不能改变顺序，

	var path []int
	var res [][]int
	//nums = quicksort(nums)
	backtracking(nums, &path, &res, -200) // 范围是【-100， 100】,传入一个不在区间的数字就不会重复
	return res
}

func backtracking(nums []int, path *[]int, res *[][]int, last int) {
	if len(nums) == 0 {
		return
	}

	used := make(map[int]bool)
	for i:=0; i<len(nums); i++ {
		if used[nums[i]] {
			continue
		}
		if nums[i] < last{
			continue
		}

		*path = append(*path, nums[i])
		used[nums[i]] = true
		if len(*path) > 1 {
			var copypath = make([]int, len(*path))
			copy(copypath, *path)
			*res = append(*res, copypath)
		}
		backtracking(nums[i+1 : ], path, res, nums[i])
		*path = (*path)[0 : len(*path) - 1]
	}
	return
}

func backtracking(nums []int, path *[]int, res *[][]int, startidx int) {
	if startidx == len(nums) {
		return
	}

	used := make(map[int]bool)
	for i:=startidx; i<len(nums); i++ {
		if used[nums[i]] {
			continue
		}
		
		// 注意不是对比相邻元素，而是对比当前元素与路径最后一个元素
		if  len(*path) > 0  && nums[i] < (*path)[len(*path) - 1]{
			continue
		}

		*path = append(*path, nums[i])
		used[nums[i]] = true
		if len(*path) > 1 {
			var copypath = make([]int, len(*path))
			copy(copypath, *path)
			*res = append(*res, copypath)
		}
		backtracking(nums, path, res, i+1)
		*path = (*path)[0 : len(*path) - 1]
	}
	return
}

46 全排列

func permute(nums []int) [][]int {
	// 组合问题相比排列问题，递归时候传入的数组不是nums[i+1: ], 而是nums.Remove(nums[i])
	var path []int
	var res [][]int
	backtracking(nums, &path, &res)
	return res
}

func backtracking(nums []int, path *[]int, res *[][]int) {
	if len(nums) == 0 {
		var copyPath = make([]int, len(*path))
		copy(copyPath, *path)
		*res = append(*res, copyPath)
		return
	}

	for i:=0; i<len(nums); i++{
		*path = append(*path, nums[i])
		// 新的数组要去除nums[i], 但是要包含其他的元素
		//在 Go 中，切片操作 nums[a:b] 是合法的，只要满足以下条件：
		//0 <= a <= b <= len(nums)
		//nums[a:b] 返回从索引 a 开始到索引 b-1 结束的子切片。

		//var newNums = make([]int, len(nums) - 1)
		//copy(newNums, nums[0: i])
		//copy(newNums[i: ], nums[i+1: ])

		var newNums []int
		newNums = append(newNums, nums[0 : i]...)
		newNums = append(newNums, nums[i+1: ]...)
		backtracking(newNums, path, res)
		*path = (*path)[ : len(*path) - 1]
	}
	return
}
// 两个易错点，newnums声明如果放到for循环外面可能出现错误，多次append导致newnums不断累加
// 第二点易错，使用copy函数注意第二个copy dst是newnums[i: ] 而不是newnums, 这样会覆盖第一个copy结果

全排列2

func permuteUnique(nums []int) [][]int {
	// 组合问题相比排列问题，递归时候传入的数组不是nums[i+1: ], 而是nums.Remove(nums[i])
	var path []int
	var res [][]int
	backtracking(nums, &path, &res)
	return res
}

func backtracking(nums []int, path *[]int, res *[][]int) {
	if len(nums) == 0 {
		var copyPath = make([]int, len(*path))
		copy(copyPath, *path)
		*res = append(*res, copyPath)
		return
	}

	var used = make(map[int]bool)
	for i:=0; i<len(nums); i++{
		if used[nums[i]] {
			continue
		}
		used[nums[i]] = true
		*path = append(*path, nums[i])
		var newNums []int
		newNums = append(newNums, nums[0 : i]...)
		newNums = append(newNums, nums[i+1: ]...)
		backtracking(newNums, path, res)
		*path = (*path)[ : len(*path) - 1]
	}
	return
}
// 相比上一题，加了一个used数组保存使用过的元素