Page Comparison

...

https://leetcode.com/problems/permutations-ii/description/

...

标准全排列算法之所以出现重复，是因为把相同元素形成的排列序列视为不同的序列，但实际上它们应该是相同的；而如果固定相同元素形成的序列顺序，当然就避免了重复。

那么反映到代码上，你注意看这个剪枝逻辑：

Code Block

// 新添加的剪枝逻辑，固定相同的元素在排列中的相对位置
if (i > 0 && nums[i] == nums[i - 1] && !used[i - 1]) {
    // 如果前面的相邻相等元素没有用过，则跳过
    continue;
}
// 选择 nums[i]

当出现重复元素时，比如输入 nums = [1,2,2',2'']，2' 只有在 2 已经被使用的情况下才会被选择，同理，2'' 只有在 2' 已经被使用的情况下才会被选择，这就保证了相同元素在排列中的相对位置保证固定。

Code Block

language	go

func permuteUnique(nums []int) (result [][]int) {
    used := make([]bool, 9)
    prev := make([]int, 0, 8)
    
    sort.Ints(nums)
    
    var backtrack func()
    backtrack = func() {
        if len(prev) == len(nums) {
            result = append(result, append([]int(nil), prev...))
            return
        }
        
        for i := 0; i < len(nums); i++ {
            num := nums[i]
            
            if i > 0 && nums[i] == nums[i-1] && !used[i-1] {
                continue
            }
            
            if used[i] {
                continue
            }
            
            prev = append(prev, num)
            used[i] = true
            
            backtrack()
            
            prev = prev[:len(prev)-1]
            used[i] = false
        }
    }
    backtrack()
    
    return
}

另一种剪枝思路

Code Block

language	go

func permuteUnique(nums []int) (result [][]int) {
    used := make([]bool, 9)
    prev := make([]int, 0, 8)
    
    sort.Ints(nums)
    
    var backtrack func()
    backtrack = func() {
        if len(prev) == len(nums) {
            result = append(result, append([]int(nil), prev...))
            return
        }
        
        prevNum := 1024
        for i := 0; i < len(nums); i++ {
            num := nums[i]
            
            if used[i] || num == prevNum {
                continue
            }
            
            prev = append(prev, num)
            used[i] = true
            prevNum = num
            
            backtrack()
            
            prev = prev[:len(prev)-1]
            used[i] = false
        }
    }
    backtrack()
    
    return
}

元素无重可复选

[组合/子集] LC 39. Combination Sum 组合总和

https://leetcode.com/problems/combination-sum/description/

Code Block

language	go

func combinationSum(candidates []int, target int) (result [][]int) {
    var prev []int
    var prevSum int
    
    var backtrack func(start int)
    backtrack = func(start int) {
        if prevSum == target {
            result = append(result, append([]int(nil), prev...))
        }
        if prevSum >= target {
            return
        }
        
        for i := start; i < len(candidates); i++ {
            prev = append(prev, candidates[i])
            prevSum += candidates[i]
            
            backtrack(i)
            
            prev = prev[:len(prev)-1]
            prevSum -= candidates[i]
        }
    }
    backtrack(0)
    
    return
}

[排列]

标准的全排列算法利用 used 数组进行剪枝，避免重复使用同一个元素。如果允许重复使用元素的话，直接放飞自我，去除所有 used 数组的剪枝逻辑就行了。

Code Block

func permuteRepeat(nums []int) [][]int {
    var res [][]int
    var track []int
    
    backtrack(nums, &res, track)
    
    return res
}

// 回溯算法核心函数
func backtrack(nums []int, res *[][]int, track []int) {
    // base case，到达叶子节点
    if len(track) == len(nums) {
        // 收集叶子节点上的值
        tmp := make([]int, len(track))
        copy(tmp, track)
        *res = append(*res, tmp)
        return
    }

    // 回溯算法标准框架
    for i := 0; i < len(nums); i++ {
        // 做选择
        track = append(track, nums[i])
        // 进入下一层回溯树
        backtrack(nums, res, track)
        // 取消选择
        track = track[:len(track)-1]
    }
}

Versions Compared

Old Version 3

New Version Current

Key

元素无重可复选

[组合/子集] LC 39. Combination Sum 组合总和

[排列]