day29| 491+46+47

491. 递增子序列

题目简述：

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

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

思路：

关键在去重

利用官方题解给的思路：判断当前遍历到的数字与上一次被选的数字是否相等

1. 若相等，则不能不选当前数字

2. 若不等，方可考虑不选当前数字

代码如下：

class Solution:
    def findSubsequences(self, nums: List[int]) -> List[List[int]]:

        def dfs(i, tmp):
            if i == len(nums):
                if len(tmp) >= 2:
                    res.append(tmp[:])      # 拷贝，tmp[:]而非tmp
                return
            
            # 选 nums[i]
            if not tmp or nums[i]>=tmp[-1]: # 需满足递增
                tmp.append(nums[i])         # 选nums[i]
                dfs(i+1, tmp)
                tmp.pop()                   # 回溯复原
                # dfs(i+1, tmp+[nums[i]])   # 与以上三行等价
            
            # 不选 nums[i]：
            # 只有在nums[i]不等于前一项tmp[-1]的情况下才考虑不选nums[i]
            # 即若nums[i] == tmp[-1]，则必考虑选nums[i]，不予执行不选nums[i]的情况
            if not tmp or (tmp and nums[i] != tmp[-1]): # 避免重复
                dfs(i+1, tmp)


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

46. 全排列

题目简述：

给定一个不含重复数字的数组 nums ，返回其 所有可能的全排列 。你可以 按任意顺序 返回答案。

思路：

不断交换，输出nums

代码如下：

class Solution:
    def permute(self, nums: List[int]) -> List[List[int]]:

    

        def backtrack(first = 0):
            # 所有数都填完了
            if first == n:  
                res.append(nums[:])
            for i in range(first, n):
                # 动态维护数组
                nums[first], nums[i] = nums[i], nums[first]
                # 继续递归填下一个数
                backtrack(first + 1)
                # 撤销操作
                nums[first], nums[i] = nums[i], nums[first]
        
        n = len(nums)
        res = []
        backtrack()
        return res

47. 全排列II

题目简述：

给定一个可包含重复数字的序列 nums ，按任意顺序 返回所有不重复的全排列。

思路：

1. 多加一个used数组记录元素使用情况

2. 利用used数组，在回溯过程中执行剪枝操作

代码如下：

class Solution:
    def permuteUnique(self, nums: List[int]) -> List[List[int]]:
        def backtrace(first,path,nums,check):
            if first==n:
                res.append(path[:])
                return
            
            for i in range(n):
                if check[i]==1:
                    continue
                if i>0 and nums[i-1]==nums[i] and check[i-1]==0:
                    continue
                
                check[i]=1
                backtrace(first+1,path+[nums[i]],nums,check)
                check[i]=0
                
        n=len(nums)
        nums.sort()
        check=[0 for _ in range(n)]
        res=[]
        backtrace(0,[],nums,check)
        return res

总结：

1. 如何巧妙设计取值的方式和回溯的方式是一个大难点

2. 如何剪枝也是一个难点