47.M 全排列 II

Problem: 47. 全排列 II

思路

对于有重复数字的情况，需要先对数组进行排序。

要解决重复问题，我们只要设定一个规则，保证在填第 idx 个数的时候重复数字只会被填入一次即可。而在本题解中，我们选择对原数组排序，保证相同的数字都相邻，然后每次填入的数一定是这个数所在重复数集合中「从左往右第一个未被填过的数字」

Code

func permuteUnique(nums []int) [][]int {
	sort.Ints(nums)
	var ans [][]int
	var path []int
	var vis = make([]bool, len(nums))
	backtrack(nums, 0, vis, path, &ans)
	return ans
}

func backtrack(nums []int, start int, vis []bool, path []int, ans *[][]int) {
	if len(path) == len(nums) {
		*ans = append(*ans, append([]int{}, path...))
		return
	}
	
	for i := 0; i < len(nums); i++ {
		if vis[i] || (i > 0 && nums[i] == nums[i-1] && !vis[i-1]) {
			continue
		}

		vis[i] = true
		path = append(path, nums[i])
		backtrack(nums, start+1, vis, path, ans)
		vis[i] = false
		path = path[0 : len(path)-1]
	}
}