LeetCode47-全排列II（Golang）
LeetCode47-全排列II
题意：
给定一个nums数组，可能存在重复数字，要求给出这个数组的全排列，且要求给出的全排列不存在重复情况。
思路：
- 本题与LC46（LC46题记）类似，利用深度优先搜索（DFS）进行求解。
- 但是因为存在重复的数字，就需要引入一些条件判断。
- 首先将nums数组进行排序，
- 考虑要去除重复的情况，我们可以限制对于重复数字的搜索过程，只能是从前向后，不能是从后向前，
- 枚举每一位时，加入如下判断：若 nums[i] 未被访问且 nums[i]==nums[i-1] 且 nums[i-1] 为被访问，则剪去对这一位的枚举。（这样就可以剪去对从后向前的搜索）
对于第5步的解释：
- 因为此时， nums[i]==nums[i-1] ，且 nums[i-1] 未被访问，如果不剪去，就将导致下一层搜索，有可能访问到 nums[i-1] （此时的搜索序为 nums[i]->nums[i-1] ），而上一轮对 nums[i-1] 搜索时候已经有过： nums[i-1]->nums[i] ，故需要将这一情况剪枝。
代码（Golang）：
func permuteUnique(nums []int) [][]int { tmp:=make([]int,0) ans:=make([][]int,0) vis:=make([]bool,len(nums)) sort.Ints(nums) var dfs func(now int) dfs=func(now int){ if now==len(nums){ ans=append(ans,append([]int(nil),tmp...)) return } for i:=0;i0 && nums[i]==nums[i-1] && !vis[i-1]){ continue } vis[i]=true tmp=append(tmp,nums[i]) dfs(now+1) vis[i]=false tmp=tmp[:len(tmp)-1] } } dfs(0) return ans}