491.递增子序列

本题和大家刚做过的 90.子集II 非常像，但又很不一样，很容易掉坑里。

https://programmercarl.com/0491.递增子序列.html

视频讲解：https://www.bilibili.com/video/BV1EG4y1h78v
给你一个整数数组 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]]

思考

这道题不能排序，要保持原始顺序，所以使用set进行去重。

class Solution:
    def findSubsequences(self, nums: List[int]) -> List[List[int]]:
        path = []
        res_all = []
        def backtracking(nums,start_index):
            if len(path) >=2:
                res_all.append(path[:])
            used_set = set()
            for i in range(start_index,len(nums)):
                #if len(path) == 0 or (nums[i] not in used_set and nums[i] >= path[-1]):
                if (path and nums[i]<path[-1]) or (nums[i] in used_set):
                    continue 
                used_set.add(nums[i])
                path.append(nums[i])
                backtracking(nums,i+1)
                path.pop()               
        backtracking(nums,0)
        return res_all

46.全排列

本题重点感受一下，排列问题 与 组合问题，组合总和，子集问题的区别。 为什么排列问题不用 startIndex
https://programmercarl.com/0046.全排列.html
视频讲解：https://www.bilibili.com/video/BV19v4y1S79W

47.全排列 II

本题 就是我们讲过的 40.组合总和II 去重逻辑 和 46.全排列 的结合，可以先自己做一下，然后重点看一下 文章中 我讲的拓展内容： used[i - 1] == true 也行，used[i - 1] == false 也行

https://programmercarl.com/0047.全排列II.html

视频讲解：https://www.bilibili.com/video/BV1R84y1i7Tm