LeetCode 491题 “Increasing Subsequences” 是一个中等难度的题目，主要考察的是深度优先搜索（DFS）和回溯算法。题目要求找到给定数组中的所有递增子序列。

题目描述

给定一个整型数组，你的任务是找到所有的递增子序列，递增子序列的长度至少为2。

示例

输入: [4, 6, 7, 7] 输出: [[4, 6], [4, 7], [4, 6, 7], [4, 6, 7, 7], [6, 7], [6, 7, 7], [7,7], [4,7,7]]

解题思路

1. 深度优先搜索（DFS）：通过递归的方式遍历所有可能的子序列。
2. 回溯：在递归过程中，如果当前子序列不再满足递增条件，则回溯到上一步。
3. 去重：使用集合来避免重复的子序列。

详细步骤

1. 初始化：定义一个结果集 res 和一个临时路径 path。
2. 递归函数：定义一个递归函数 dfs(start)，从数组的 start 位置开始搜索。
3. 递归终止条件：当遍历到数组末尾时，检查 path 的长度是否大于1，如果是则加入结果集。
4. 递归逻辑：
   • 遍历从 start 到数组末尾的所有元素。
   • 如果当前元素可以加入 path（即当前元素大于 path 的最后一个元素或者 path 为空），则将其加入 path 并继续递归。
   • 递归结束后，回溯，即从 path 中移除当前元素。

代码实现

def findSubsequences(nums): def dfs(start, path): if len(path) > 1: res.append(path[:]) used = set() for i in range(start, len(nums)): if nums[i] in used: continue if not path or nums[i] >= path[-1]: used.add(nums[i]) dfs(i + 1, path + [nums[i]])

res = []
dfs(0, [])
return res

nums = [4, 6, 7, 7] print(findSubsequences(nums))

代码解释

1. findSubsequences 函数：主函数，初始化结果集 res 并调用 dfs 函数。
2. dfs 函数：
   • start：当前开始搜索的位置。
   • path：当前递增子序列。
   • used：用于去重的集合，避免在同一层递归中使用相同的元素。
3. 递归逻辑：
   • 遍历从 start 到数组末尾的所有元素。
   • 如果当前元素未在当前层使用过，并且可以加入 path，则加入 path 并继续递归。
   • 递归结束后，回溯。

复杂度分析

• 时间复杂度：O(2^N)，在最坏情况下，每个元素都有两种选择（加入或不加入子序列）。
• 空间复杂度：O(N)，递归栈的深度最多为 N。

通过上述步骤和代码实现，可以有效地找到数组中的所有递增子序列。希望这个详细的解答对你有所帮助！如果有任何进一步的问题，欢迎继续提问。