代码随想录算法训练营第25天—回溯算法05 | *491.递增子序列 *46.全排列 47.全排列 II

*491.递增子序列

https://programmercarl.com/0491.%E9%80%92%E5%A2%9E%E5%AD%90%E5%BA%8F%E5%88%97.html
视频讲解：https://www.bilibili.com/video/BV1EG4y1h78v

考点
- 回溯+子集+去重
我的思路
- 暴力法，不进行去重，仅在最后加入结果时判断当前子序列是否之前出现过
- 能通过力扣，但是效率排在后10%
视频讲解关键点总结
- 重点在于去重逻辑和判断递增子序列的逻辑
- 去重逻辑：由于本题的数组不是有序数组，因此对于重复的元素，需要使用的判断条件是其是否在同一树层出现过，而不是同一树层的前一元素；为此，需要使用哈希结构（数组或集合）记录同一树层中已出现元素的情况
- 判断递增子序列的逻辑：在将当前元素加入子序列之前，先判断该元素是否小于子序列的最后一个元素，如果小于，就跳过当前元素；这样，所得到的所有子序列就全都是递增的了，不需要进行额外判断，能提升一些效率
我的思路的问题
- 运行效率慢
代码书写问题
- list.sort()没有返回值，因此想要把排序后的列表和其它列表进行比对，要先进行sort，再用列表本身进行对比
可执行代码

# 暴力法
class Solution:
    def backtracking(self, nums, sequence, result, start_index):
        if start_index == len(nums):
            return
        for i in range(start_index, len(nums)):
            sequence.append(nums[i])
            cur = sequence[:]
            cur.sort()
            if len(sequence) >= 2 and cur == sequence and sequence not in result:
                result.append(sequence[:])
            self.backtracking(nums, sequence, result, i + 1)
            sequence.pop()

    def findSubsequences(self, nums: List[int]) -> List[List[int]]:
        result = []
        self.backtracking(nums, [], result, 0)
        return result

# 过程去重版（去掉了判断sequence in result，效率提升70-80倍）
class Solution:
    def backtracking(self, nums, sequence, result, start_index):
        used = set()
        if start_index == len(nums):
            return
        for i in range(start_index, len(nums)):
            if sequence and nums[i] < sequence[-1]:
                continue
            elif nums[i] in used:
                continue
            used.add(nums[i])
            sequence.append(nums[i])
            if len(sequence) >= 2:
                result.append(sequence[:])
            self.backtracking(nums, sequence, result, i + 1)
            sequence.pop()

    def findSubsequences(self, nums: List[int]) -> List[List[int]]:
        result = []
        self.backtracking(nums, [], result, 0)
        return result

*46.全排列

https://programmercarl.com/0046.%E5%85%A8%E6%8E%92%E5%88%97.html
视频讲解：https://www.bilibili.com/video/BV19v4y1S79W

考点
- 回溯+排列
我的思路
- 无思路
视频讲解关键点总结
- 排列问题也是依次取值然后逐步生成完整的排列
- 回溯三要素
  - 形参：候选数组，候选数组使用情况used，单个排列，结果变量；返回值为空
  - 退出条件：当单个排列的长度等于候选数组时，将排列加入结果并返回
  - 回溯逻辑
    - 循环范围为候选数组：
      - 如果当前元素已经被使用过了（used对应标志位为1），则跳过当前元素
      - 将当前元素的used数组对应位置标记为1
      - 当前元素加入排列
      - 递归
      - 当前元素弹出
      - used标记位改回0
我的思路的问题
- 无思路
代码书写问题
- 无
可执行代码

class Solution:
    def backtracking(self, nums, used, permutation, result):
        if len(permutation) == len(nums):
            result.append(permutation[:])
            return
        for i in range(len(nums)):
            if used[i] == 1:
                continue
            used[i] = 1
            permutation.append(nums[i])
            self.backtracking(nums, used, permutation, result)
            permutation.pop()
            used[i] = 0

    def permute(self, nums: List[int]) -> List[List[int]]:
        result = []
        used = [0] * len(nums)
        self.backtracking(nums, used, [], result)
        return result

47.全排列 II

https://programmercarl.com/0047.%E5%85%A8%E6%8E%92%E5%88%97II.html
视频讲解：https://www.bilibili.com/video/BV1R84y1i7Tm

考点
- 回溯+排列+去重
我的思路
- 本题就是在上一题的基础上，加上树层去重即可
视频讲解关键点总结
- 和我的思路一致
我的思路的问题
- 无
代码书写问题
- 无
可执行代码

class Solution:
    def backtracking(self, nums, used, permutation, result):
        if len(permutation) == len(nums):
            result.append(permutation[:])
            return
        for i in range(len(nums)):
            if used[i] == 1 or (i > 0 and nums[i] == nums[i - 1] and used[i - 1] == 0):
                continue
            used[i] = 1
            permutation.append(nums[i])
            self.backtracking(nums, used, permutation, result)
            permutation.pop()
            used[i] = 0

    def permuteUnique(self, nums: List[int]) -> List[List[int]]:
        nums.sort()
        result = []
        used = [0] * len(nums)
        self.backtracking(nums, used, [], result)
        return result