代码随想录 - Day34 - 回溯：递增子序列+排列问题

代码随想录 - Day34 - 回溯：递增子序列+排列问题

491. 递增子序列

如果有相等的整数也算递增序列
递增子序列中至少有两个元素 (遍历的时候不用遍历nums中最后一个元素)

输入：nums = [4,6,6,2,8]
输出：[[4,6],[4,6,6],[4,6,6,8],[4,6,8],[4,8],[6,6],[6,6,8],[6,8],[2,2],[2,2,8],[2,8]]
1
2

class Solution:
    def backtracking(self, nums, startIndex, path, result):
        if len(path) > 1:
            result.append(path[:])
            # 注意这里不要加return，因为要取树上的节点

        uset = set()    # 用set()对本层元素去重
        for i in range(startIndex, len(nums)):
            # 排除重复的情况，跳过递减的情况
            if (path and nums[i] < path[-1]) or (nums[i] in uset):
                continue
            uset.add(nums[i])       # 记录这个元素在本层用过了，本层后面不能再用了
            path.append(nums[i])
            self.backtracking(nums, i + 1, path, result)    # 递归
            path.pop()  # 回溯

    def findSubsequences(self, nums: List[int]) -> List[List[int]]:
        result = []
        self.backtracking(nums, 0, [], result)
        return result
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20

题目说了数值范围，所以还可以用哈希表去重，速度比set()快很多。
但是，个人觉得没必要，因为放在实际情况中一般不会给数值范围。

class Solution:
    def backtracking(self, nums, startIndex, path, result):
        if len(path) > 1:
            result.append(path[:])
            # 注意这里不要加return，因为要取树上的节点

        used = [0] * 201  # 使用数组来进行去重操作，题目说数值范围[-100, 100]
        for i in range(startIndex, len(nums)):
            # 排除重复的情况，跳过递减的情况
            # 这里是利用数组的下标和数组中存储的元素来进行去重
            if (path and nums[i] < path[-1]) or used[nums[i] + 100] == 1:
                continue
            used[nums[i] + 100] = 1  # 标记当前元素已经使用过
            path.append(nums[i])
            self.backtracking(nums, i + 1, path, result)    # 递归
            path.pop()  # 回溯

    def findSubsequences(self, nums: List[int]) -> List[List[int]]:
        result = []
        self.backtracking(nums, 0, [], result)
        return result
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21

46.全排列

全排列，即[1,2]和[2,1]算作两种排列，所以这道题的result要收集所有的叶子节点
nums 中的所有整数互不相同，因此无需考虑去重

输入：nums = [1,2,3]
输出：[[1,2,3],[1,3,2],[2,1,3],[2,3,1],[3,1,2],[3,2,1]]
1
2

这种题就要考虑新的问题了，即它每次的startIndex都是固定的，遇到取过的数时则需要跳过

class Solution:
    def backtracking(self, nums, used, path, result):
        if len(path) == len(nums):
            result.append(path[:])
            return

        for i in range(len(nums)):
            if used[i]:     # 遇到取过的数时则需要跳过
                continue
            used[i] = True  # 取过的数设为True
            path.append(nums[i])
            self.backtracking(nums, used, path, result)
            path.pop()      # 回溯
            used[i] = False # 回溯后把该数设回False

    def permute(self, nums: List[int]) -> List[List[int]]:
        result = []
        used = [False] * len(nums)
        self.backtracking(nums, used, [], result)
        return result
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20

考虑跳过用过的数时，脑子里第一反应是dict，却忘记了用更为简单的数组也可以…

47. 全排列 II

相较于上一题，需要考虑去重的问题，dict貌似有用武之地了

输入：nums = [1,2,1]
输出：[[1,1,2], [1,2,1], [2,1,1]]
1
2

class Solution:
    def backtracking(self, nums, used, path, result):
        if len(path) == len(nums):
            result.append(path[:])
            return

        for i in range(len(nums)):
            # 要去重的是 用过且重复 的数
            if i > 0 and nums[i] == nums[i - 1] and used[i - 1] == False:
                continue
            if used[i] == False:     # 遇到取过的数时则需要跳过
                used[i] = True  # 取过的数设为True
                path.append(nums[i])
                self.backtracking(nums, used, path, result)
                path.pop()      # 回溯
                used[i] = False # 回溯后把该数设回False

    def permuteUnique(self, nums: List[int]) -> List[List[int]]:
        result = []
        used = [False] * len(nums)
        nums.sort()             # 提前排好序，方便后续去重
        self.backtracking(nums, used, [], result)
        return result
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23

感觉今天这几道题思路好想，代码不好写，总会在一些细节上出错，需要多练习。

以及，mermaid画图好麻烦。。