leetcode_回溯法合集

2 minutes read
LeetCode
面试 • 算法 • 数据结构

46. 全排列

46. 全排列

Difficulty: 中等

给定一个 没有重复 数字的序列，返回其所有可能的全排列。

示例:

输入: [1,2,3]
输出:
[
  [1,2,3],
  [1,3,2],
  [2,1,3],
  [2,3,1],
  [3,1,2],
  [3,2,1]
]

Solution1 普通递归

Language: Go

func permute(nums []int) [][]int {
    if len(nums) == 1 {
        return [][]int{nums}
    }

    var ret [][]int // 结果
    for k, v := range nums {
        // 1. 提取出当前位
        // eg: [1, 2, 3] 提取出[1, 3]
        tmp := make([]int, len(nums)-1)
        copy(tmp, nums[:k])
        copy(tmp[k:], nums[k+1:])

        // 2. 拿去求排列 [1, 3] [3, 1]
        sub := permute(tmp)
        // 3. 结果放入res返回
        for _, s := range sub {
            // res = [[1,3,2], [3,1,2]]
            res = append(res, append(s, v))
        }
    }
    return res
}

Solution2 回溯

Language: Go

func permute(nums []int) [][]int {
    if len(nums) == 1 {
        return [][]int{nums}
    }
    l := len(nums)
    
    res := [][]int{}
    for i := 0; i < l; i++ {
        // [1, 2, 3] 比如把2提取出来
        tmp := make([]int, l-1)
        copy(tmp, nums[:i])
        copy(tmp[i:], nums[i+1:])
        // tmp此时为[1,3]
        
        // 把[1,3]拿过去排列，结果肯定是[1,3] [3,1]
        sub := permute(tmp)
        for _, v := range sub {
            // 遍历[1,3] [3,1], 把 2 加到后面
            res = append(res, append(v, nums[i]))
        }
    }
    return res
}

func permute(nums []int) [][]int {
    if len(nums) == 1 {
        return [][]int{nums}
    }
    l := len(nums)
    var (
        res [][]int                 // 返回结果
        tmp = make([]int, 0, l)     // 中间值
        tk  = make(map[int]bool, l) // 记录已经使用的数字
    )
    return trackBack()
}

func trackBack(nums, tmp []int, ret [][]int, tk map[int]bool) [][]int {
    // 递归出口
    if len(nums) == len(tmp) {
        c := make([]int, len(tmp))
        copy(c, tmp)
        // 4. ret[[3,6,9]]
        ret = append(ret, c)
        return ret
    }
    // [3, 6, 9]
    for _, v := range nums {
        //  回溯检查
        if tk[v] {
            continue
        }

        // 1. 做标记 tmp[3] map[3]=true
        // 2. 做标记 tmp[3,6] map[6]=true
        // 3. 做标记 tmp[3,6,9] map[9]=true
        tmp = append(tmp, v)
        tk[v] = true
        ret = trackBack(nums, tmp, ret, tk)
        // 清除
        tk[v] = false
        tmp = tmp[:len(tmp)-1]
    }
    return ret
}

分享：