递增子序列

Leetcode Link: 491. 递增子序列 - 力扣（LeetCode）

题目

给你一个整数数组 nums ，找出并返回所有该数组中不同的递增子序列，递增子序列中 至少有两个元素 。你可以按 任意顺序 返回答案。

数组中可能含有重复元素，如出现两个整数相等，也可以视作递增序列的一种特殊情况。

 

本题属于子集问题，不过是有条件的子集问题

解法一

思路：回溯法中的子集问题

显然，本题也同样需要去重，但是不同于子集II，根据本题的要求，本题是不能通过排序进行去重的，因此如果对每一层的子树进行去重，需要用到集合 set() 来完成

满足要求的答案：

1. len(path)>=2 并且 path 内容非降序

停止回溯的条件：

1. choose 为空

剪枝&去重：

1. 当前的值 val 在当前层内已经被使用过了 (val in used == True)，就 continue
2. 当前值 val 放进 path 后 path 不再是有序的，continue（实际上是不满足题目要求的剪枝）

题解：

class Solution:
    def findSubsequences(self, nums: List[int]) -> List[List[int]]:
        def backtracking(choose):
            nonlocal res, path
		    # 用来剪枝&去重
            used = set()
            # 满足题目条件
            if len(path) >= 2:
                res.append(copy.deepcopy(path))
            # 终止回溯条件
            if choose == []:
                return
            
            for idx, val in enumerate(choose):
                # 剪枝 & 去重
                if val in used: # 使用过了
                    continue
                # 剪枝，不满足题目条件不用管
                if path != [] and val < path[-1]:
                    continue
                
                used.add(val) # 用过的，加到used里面
                path.append(val)
                backtracking(choose[idx+1:])
                path.pop()
 
        res = []
        path = []
        backtracking(nums)
        return res

---

复习时遇到了错误，

实际上我也发现同一层需要去重了，但是我的去重手段是 last_num != nums[next_i]，并及时更新last_num。然而这种去重方式是错误的

一般用这种方式去重的情况往往是有序的输入，即相同的数字只可能相邻。而在本问题中，相同的数字可能不相邻，所以必须用一个 set() 来筛选

下面贴正确的代码

class Solution:
    def findSubsequences(self, nums: List[int]) -> List[List[int]]:
        path = [-float('inf')] # 先放一个防止path[-1]报错
        res = []
 
        def backtracking(i):
            if i >= len(nums):
                return
	        # 题目要求至少俩，所以这里至少仨
            if len(path) >= 3:
                res.append(path[1:].copy())
            
            used = set()
            last_num = -float('inf')
            for next_i in range(i+1, len(nums)):               
                if nums[next_i] not in used and nums[next_i] >= path[-1]:
                    used.add(nums[next_i])
                    path.append(nums[next_i])
                    backtracking(next_i)
                    path.pop()
 
        backtracking(-1)
        return res

启发和联系