发现又涨了一个粉丝，心情愉悦
491.递增子序列
题目链接491. 非递减子序列 - 力扣（LeetCode）
思路
首先也是要求全部子集
然后我们根据题目条件筛选
要不递减，长度大于等于2，不重复
提交
效率低，但是思路简单粗暴
class Solution: def findSubsequences(self, nums: List[int]) -> List[List[int]]: res = [] def backtrack(start: int, path: List[int]): path_sort=sorted(path) if len(path)>=2 and path==path_sort and path not in res: res.append(path.copy()) # 从start开始遍历，避免重复子集 for i in range(start, len(nums)): path.append(nums[i]) # 选择当前元素 backtrack(i + 1, path) # 递归（不能重复选自己） path.pop() # 回溯，撤销选择 backtrack(0, []) return res46.全排列
题目链接46. 全排列 - 力扣（LeetCode）
思路
感觉是一个典中典的题，但是我没背过它的代码，自己想还是想不出来。
这是回溯法最经典的题型，和子集、IP 复原思路同源，但核心区别：全排列要用完所有元素，且顺序不同算不同结果。
核心思路
每次从所有未用过的数字里选一个加入路径
用used 数组标记数字是否被使用（避免重复选）
当路径长度 = 数组长度时，就是一个完整排列
回溯：撤销选择，继续尝试其他可能
妙啊，用一个数组把使用未使用做标记
提交
from typing import List class Solution: def permute(self, nums: List[int]) -> List[List[int]]: res = [] n = len(nums) # 标记数字是否被使用 used = [False] * n def backtrack(path): # 终止条件：路径长度等于数组长度，找到一个全排列 if len(path) == n: res.append(path.copy()) return # 每次都遍历所有数字（和子集不同，子集是从start开始） for i in range(n): if not used[i]: # 没被使用才选 used[i] = True # 标记为已使用 path.append(nums[i]) backtrack(path) # 递归 path.pop() # 回溯：撤销选择 used[i] = False # 取消标记 backtrack([]) return res47.全排列 II
题目链接47. 全排列 II - 力扣（LeetCode）
思路
就是在上道题的基础上去重
那在收集结果的时候加一下判断条件就好了
只改了这一句
if len(path)==n and path not in res:
提交
class Solution: def permuteUnique(self, nums: List[int]) -> List[List[int]]: res=[] n=len(nums) used=[False]*n def backtrack(path): if len(path)==n and path not in res: res.append(path[:]) return for i in range(n): if not used[i]: path.append(nums[i]) used[i]=True backtrack(path) path.pop() used[i]=False backtrack([]) return res)
