【代码随想录】算法训练计划28

回溯

1、491. 递增子序列

题目：
给你一个整数数组 nums ，找出并返回所有该数组中不同的递增子序列，递增子序列中 至少有两个元素 。你可以按 任意顺序 返回答案。
数组中可能含有重复元素，如出现两个整数相等，也可以视作递增序列的一种特殊情况。

思路：

• if len(list)==0
• 去重，很经典的去重方法,但这次去重不一样了，是在内部写的 used，真的是不带入例子很难理解
• 不是if len(list)==0 || nums[i] >= nums[i-1] {，是 nums[i] >= list[len(list)-1]

func findSubsequences(nums []int) [][]int {
    // 代码一刷
    list := []int{}
    res := make([][]int, 0)
    var backtrack func(res *[][]int, list,nums []int, index int)
    backtrack = func(res *[][]int, list,nums []int, index int) {
        if len(list) >= 2 {
            ans := make([]int, len(list))
            copy(ans, list)
            *res = append(*res, ans)
        }
        used := make(map[int]bool, len(nums))
        for i:=index; i<len(nums); i++ {
            if used[nums[i]] {
                continue
            }
            if len(list)==0 || nums[i] >= list[len(list)-1] {
                used[nums[i]] = true
                list = append(list, nums[i])
                backtrack(res, list, nums, i+1)
                list = list[:len(list)-1]
            }
        }
    }
    backtrack(&res, list, nums, 0)
    return res
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27

2、46. 全排列

题目：
给定一个不含重复数字的数组 nums ，返回其 所有可能的全排列 。你可以 按任意顺序 返回答案。
输入：nums = [1,2,3]
输出：[[1,2,3],[1,3,2],[2,1,3],[2,3,1],[3,1,2],[3,2,1]]

思路：

• 其实难点就在于这个选择列表，理解记忆一下,带入秒懂，画图

func permute(nums []int) [][]int {
    // 代码二刷
    res := [][]int{}
    list := []int{}
    vis := make([]bool, len(nums))
    backtrack(&res, list,nums, vis)
    return res
}
func backtrack(res *[][]int, list []int ,nums []int, vis []bool) {
    if len(list) == len(nums) {
        ans := make([]int, len(list))
        copy(ans, list)
        *res = append(*res, ans)
        return
    }
    for i:=0; i<len(nums); i++ {
        if vis[i] {
            continue
        }
        list = append(list, nums[i])
        vis[i] = true
        backtrack(res, list, nums,vis)
        list = list[:len(list)-1]
        vis[i] = false
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26

3、47. 全排列 II

题目：
给定一个可包含重复数字的序列 nums ，按任意顺序 返回所有不重复的全排列。
输入：nums = [1,1,2]
输出：
[[1,1,2],
[1,2,1],
[2,1,1]]

思路：

• 去重呗,回溯玩多了，就是条件的玩法，条件和一些选择列表，以及去重方法的做法

func permuteUnique(nums []int) [][]int {
    // 代码二刷
    list := []int{}
    res := [][]int{}
    sort.Ints(nums)
    vis := make([]bool, len(nums))
    backtrack(&res, list, nums, vis)
    return res
}
func backtrack(res *[][]int, list,nums []int, vis []bool) {
    if len(list) == len(nums) {
        ans := make([]int, len(list))
        copy(ans,list)
        *res = append(*res, ans)
        return
    }
    for i:=0; i<len(nums); i++ {
        if vis[i] {
            continue
        }
        if i != 0 && nums[i] == nums[i-1] && !vis[i-1] {
            continue
        }
        list = append(list, nums[i])
        vis[i] = true
        backtrack(res, list,nums,vis)
        vis[i] = false
        list = list[:len(list)-1]
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30

4、

题目：

思路：

1

5、

题目：

思路：

1