代码随想录 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
}