文章 217
评论 7
浏览 146909
Backtracking - 47. Permutations II

Backtracking - 47. Permutations II

47. Permutations II

Given a collection of numbers that might contain duplicates, return all possible unique permutations.

Example:

Input: [1,1,2]
Output:
[
  [1,1,2],
  [1,2,1],
  [2,1,1]
]

思路:

和46题差别在于数字有重复,需要返回unique的组合,组合问题,只要有重复,通解思路都是先先排序,剩下的就基本和46题一样,还需判断一个数是否被用过来剪枝。

代码:

go:

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
}

标题:Backtracking - 47. Permutations II
作者:michael
地址:https://www.bitbo-liuyang.com/articles/2019/09/05/1567696675253.html

Nothing just happens, it's all part of a plan.

取消