47. Permutations II
Given a collection of numbers that might contain duplicates, return all possible unique permutations.
Example:
代码语言：javascript复制Input: [1,1,2]
Output:
[
[1,1,2],
[1,2,1],
[2,1,1]
]思路：
和46题差别在于数字有重复，需要返回unique的组合，组合问题，只要有重复，通解思路都是先先排序，剩下的就基本和46题一样，还需判断一个数是否被用过来剪枝。
代码：
go：
代码语言：javascript复制func permuteUnique(nums []int) [][]int {
sort.Ints(nums)
return permute(nums)
}
func permute(nums []int) [][]int {
var res [][]int
dfs(0, nums, &res)
return res
}
func dfs(start int, nums []int, res *[][]int){
if start == len(nums) {
*res = append(*res, append([]int{}, nums...))
return
}
for i := start; i < len(nums); i {
if hasUsed(nums, start, i) {
continue
}
nums[i], nums[start] = nums[start], nums[i]
dfs(start 1, nums, res)
nums[start], nums[i] = nums[i], nums[start]
}
}
func hasUsed(nums []int, i, j int) bool {
for k := i; k < j; k {
if nums[k] == nums[j] {
return true
}
}
return false
}
