代码随想录 day29 第七章 回溯算法part05

本文主要是介绍代码随想录 day29 第七章 回溯算法part05，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

• 491.递增子序列
• 46.全排列
• 47.全排列 II

1. 递增子序列

关联 leetcode 491.递增子序列

本题和大家刚做过的 90.子集II 非常像，但又很不一样，很容易掉坑里。

• 思路

  • 不能改变原数组顺序
    • 不能先排序
  • 去重
    • 同一层去重
    • 树枝上可以有重复元素
  • 新元素添加条件
    • 大于等于当前次收集数组最右元素
      • value > array[right]

• 题解

  func findSubsequences(nums []int) [][]int {rets := make([][]int, 0)ret := make([]int, 0) //从左到右一次递增var backtracking func(nums []int, startIdx int)backtracking = func(nums []int, startIdx int) {//append retsif len(ret) > 1 {tmp := make([]int, len(ret))copy(tmp, ret)rets = append(rets, tmp)}//the map to record if the value usedusedMap := make(map[int]bool)for i := startIdx; i < len(nums); i++ {curVal := nums[i]// 当前层用过了if usedMap[curVal] {continue}// 取到的数 < 最右的数if len(ret) > 0 && curVal < ret[len(ret)-1] {continue}usedMap[curVal] = trueret = append(ret, curVal)backtracking(nums, i+1)ret = ret[:len(ret)-1]}}backtracking(nums, 0)return rets
  }
  

2. 全排列

关联 leetcode 46.全排列

• 思路

  • 排列开始要考虑顺序了
    • 【1，2】和【2，1】是两个结果
    • 处理排列问题就不用 startIndex 了
    • 需要用一个 used 数组来标记元素的使用
      • 全排列，所有元素都要使用到
  • 收割点
    • 叶子节点处
    • 单层循环的 ret 里面收集的元素数量 == nums 包含的元素数量
      • 取完了这次的全排列

• 题解

  func permute(nums []int) [][]int {rets := make([][]int, 0)ret := make([]int, 0)used := make([]bool, len(nums))var backtracking func(nums []int, used []bool)backtracking = func(nums []int, used []bool) {if len(ret) == len(nums) { //完成了该轮全排列收集tmp := make([]int, len(ret))copy(tmp, ret)rets = append(rets, tmp)}for i := 0; i < len(nums); i++ {if used[i] {//该元素已经收集过了, 收集下一个continue}used[i] = true//收集新元素ret = append(ret, nums[i])backtracking(nums, used)//回溯ret = ret[:len(ret)-1]used[i] = false}}backtracking(nums, used)return rets
  }
  

3. 全排列 II

关联 leetcode 47.全排列 II

本题 就是我们讲过的 40.组合总和II 去重逻辑 和 46.全排列 的结合，可以先自己做一下，然后重点看一下 文章中 我讲的拓展内容。 used[i - 1] == true 也行，used[i - 1] == false 也行

https://programmercarl.com/0047.全排列II.html

视频讲解：回溯算法求解全排列，如何去重？| LeetCode：47.全排列 II_哔哩哔哩_bilibili

• 思路

  • 在上一道题的基础上，增加去重
    • 同一层去重
      • used[i-1]==false
      • 在一个 for 里面的元素去重
    • 树枝去重
      • used[i-1] == true
      • 会多出一些树枝衍生无用操作
  • 一定要加上 used[i - 1] == false或者used[i - 1] == true，因为 used[i - 1] 要一直是 true 或者一直是false 才可以，而不是 一会是true 一会又是false。 所以这个条件要写上
    • used[i-1] 去重
      • 要一直维持同一种 方案：
        • 树层去重
        • 树枝去重

• 题解

  func permuteUnique(nums []int) [][]int {rets := make([][]int, 0)ret := make([]int, 0)used := make([]bool, len(nums))sort.Ints(nums)var backtracking func(nums []int, curLen int)backtracking = func(nums []int, curLen int) {if curLen == len(nums) { //完成了该轮全排列收集tmp := make([]int, len(ret))copy(tmp, ret)rets = append(rets, tmp)}for i := 0; i < len(nums); i++ {// used[i - 1] == true，说明同一树枝nums[i - 1]使用过// used[i - 1] == false，说明同一树层nums[i - 1]使用过// 一定要 used[i-1] 这个判断if i > 0 && nums[i] == nums[i-1] && !used[i-1] {continue}if !used[i] { //该元素已经收集过了, 收集下一个used[i] = true //收集新元素ret = append(ret, nums[i])backtracking(nums, curLen+1) //回溯ret = ret[:len(ret)-1]used[i] = false}}}backtracking(nums, 0)return rets
  }
  

  4. 题外话

  • 树层上对前一位去重非常彻底，效率很高，树枝上对前一位去重虽然最后可以得到答案，但是做了很多无用搜索

这篇关于代码随想录 day29 第七章 回溯算法part05的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！

---