难度: Medium
给你一个整数数组 nums ，找出并返回所有该数组中不同的递增子序列，递增子序列中 至少有两个元素 。你可以按 任意顺序 返回答案。
数组中可能含有重复元素，如出现两个整数相等，也可以视作递增序列的一种特殊情况。
示例 1：
输入：nums = [4,6,7,7] 输出：[[4,6],[4,6,7],[4,6,7,7],[4,7],[4,7,7],[6,7],[6,7,7],[7,7]]
示例 2：
输入：nums = [4,4,3,2,1] 输出：[[4,4]]
提示：
1 <= nums.length <= 15-100 <= nums[i] <= 100运行时间: 63 ms
内存: 21.9 MB
class Solution:
def findSubsequences(self, nums: List[int]) -> List[List[int]]:
path = []
res = []
def traceback(nums, startindex):
harshtable = {}
if len(path) > 1:
res.append(path[:])
for i in range(startindex, len(nums)):
if (path and nums[i] < path[-1]) or nums[i] in harshtable:
continue
path.append(nums[i])
harshtable[nums[i]] = 1
traceback(nums, i + 1)
path.pop(-1)
traceback(nums, 0)
return res
这个题解使用回溯法来找到所有不同的递增子序列。具体思路为： 1. 定义path数组保存当前选择的子序列，res数组保存所有合法的递增子序列。 2. 使用traceback函数进行回溯，参数为原数组nums和当前选择元素的起始下标startindex。 3. 终止条件为startindex等于nums长度，即所有元素都已遍历。 4. 在选择列表中依次选择当前下标i对应的元素： - 如果path非空且当前元素小于path最后一个元素，或者当前元素已经在本层选择过，则跳过避免重复。 - 否则将当前元素加入path，并用哈希表记录已选择过的元素。 - 进入下一层递归，下标为i+1。 - 递归返回后，从path中删除当前元素，进行回溯。 5. 在递归前，如果path长度大于1，则找到一个合法的递增子序列，将其加入res。 6. 原问题的解即为res数组。
时间复杂度: O(2^n)
空间复杂度: O(n * 2^n)
class Solution:
def findSubsequences(self, nums: List[int]) -> List[List[int]]:
path = [] # 保存当前选择的子序列
res = [] # 保存所有合法的递增子序列
def traceback(nums, startindex):
harshtable = {} # 记录本层已选择过的元素
if len(path) > 1:
res.append(path[:]) # 找到合法子序列，加入res
for i in range(startindex, len(nums)):
# 当前元素小于path最后一个元素，或者已经选择过，则跳过
if (path and nums[i] < path[-1]) or nums[i] in harshtable:
continue
path.append(nums[i]) # 选择当前元素
harshtable[nums[i]] = 1 # 记录已选择
traceback(nums, i + 1) # 进入下一层递归
path.pop(-1) # 回溯，删除当前元素
traceback(nums, 0) # 回溯起点为下标0
return res
为确保生成的子序列是递增的，算法在选择元素加入到`path`数组中之前会检查该元素是否大于或等于`path`数组中的最后一个元素。若当前元素小于`path`的最后一个元素，则该元素不会被选择，确保子序列的递增性。遇到相等的元素时，算法允许这种情况，因为非递减序列允许元素相等。这样，即使有相等的元素也可以被加入到子序列中，只要它们不破坏递增的条件。
算法通过在每一层递归中使用一个哈希表（harshtable）来避免重复生成相同的子序列。在递归的每一层中，哈希表记录了该层中已选择过的元素。如果在同一层递归中遇到已经存在于哈希表中的元素，该元素会被跳过。这样，相同的元素在同一层中不会被重复选择，从而避免生成重复的子序列。
在递归的每一层中初始化一个新的哈希表是为了确保每一层的元素选择是独立的。如果使用全局哈希表，则一旦一个元素在某一层被选择，它在整个递归过程中都不能再被选择，这会错误地限制了元素的重用可能性，尤其是在不同的递归路径中。局部哈希表确保了只在当前递归层中防止重复选择，允许同一元素在不同的子序列中的不同位置被重复使用，从而生成所有可能的递增子序列。
是的，这种方法可能会导致在递归过程中多次添加同一个子序列。这是因为每当`path`数组的长度大于1时，`path`就会被添加到`res`数组中，而这可能在递归的不同层级多次发生。然而，由于每次添加到`res`前都检查`path`的长度，且每层的选择通过哈希表限制了重复，所以实际上生成的每个子序列至少在其元素的某一位置上有所不同。如果需要进一步优化以确保`res`中不含重复子序列，可以在最终输出前对`res`进行去重处理。