非递减子序列

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

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

数组的子序列是由数组删除一些元素（也可能不删除）而不改变剩余元素顺序形成的序列。
例如，[4,6,7] 是数组 [4,5,6,7] 的一个子序列。
题目数据保证答案中至少有一个非递减子序列。

class Solution:
    def backtracking(self,nums,index,path,result):
        if len(path) > 1:
            result.append(path[:])
        set_ = set()    #!!!!!!进入下一层前重置集合，相当于只在同层里面使用set实现层去重
        for i in range(index,len(nums)):
            if (path and nums[i] < path[-1]) or nums[i] in set_:
                continue
            path.append(nums[i])
            set_.add(nums[i]) #但是往下探索返回的set不会设置成最底下的元素吗
            #不会，我的理解是for循环是分树枝，回溯函数是生长枝条，哦，used在每个函数里被创建，就属于这个函数的局部变量，所以每一层都有自己的used
            self.backtracking(nums,i+1,path,result)
            path.pop()


    def findSubsequences(self, nums: List[int]) -> List[List[int]]:
        result = []
        self.backtracking(nums,0,[],result)
        return result

主要是加了一个set来实现树层去重，注意set是在每一层递归开始时创建的

不能直接排序nums,因为排序会改变元素的相对顺序，导致错误的结果,因此这里想实现返回的是非递减子序列就要在path加元素的时候判断是否比path[-1]大

然后还有个有意思的就是实现树层去重（就是在分层的时候根节点相同的树枝就不要了），结合这几天的学习我对这种题目的理解就是————for循环是分树枝，回溯函数是生长枝条，所以在for循环里面判断是否去重，而不是在回溯函数里面判断是否去重。

那如何实现树层去重呢？

那就是用set_这个集合来实现，并且这是个局部变量（作用域在当前层，也就是在每个回溯函数中），每一层递归都会创建当层的集合，用来记录当层已经使用过的元素，从而实现树层去重。

全排列

46. 全排列(题目链接)

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

示例 1：

输入：nums = [1,2,3]

输出：[[1,2,3],[1,3,2],[2,1,3],[2,3,1],[3,1,2],[3,2,1]]

示例 2：

输入：nums = [0,1]

输出：[[0,1],[1,0]]

示例 3：

输入：nums = [1]

输出：[[1]]

class Solution:
    def backtracking(self,nums,used,path,result):
        if len(path) == len(nums):
            result.append(path[:])
        for i in range (len(nums)):
            if used[i]:
                continue
            path.append(nums[i])
            used[i] = True
            self.backtracking(nums,used,path,result)
            path.pop()
            used[i] = False
    def permute(self, nums: List[int]) -> List[List[int]]:
        result = []
        used = [False]*len(nums)
        self.backtracking(nums,used,[],result)
        return result

在排列问题上就不再需要startIndex了，因为排列是有序的，所以每次都从0开始遍历

但是选过的元素就不能再选了，所以需要一个used数组来记录哪些元素已经被选过了（类似组合问题的剪枝，每调用回溯函数就剪一条边）

全排列 II

47. 全排列 II(题目链接)
给定一个可包含重复数字的序列 nums ，按任意顺序返回所有不重复的全排列。

示例 1：

输入：nums = [1,1,2]

输出：
[[1,1,2],
[1,2,1],
[2,1,1]]

示例 2：

输入：nums = [1,2,3]

输出：[[1,2,3],[1,3,2],[2,1,3],[2,3,1],[3,1,2],[3,2,1]]

class Solution:
    def backtracking(self,nums,used,path,result):
        if len(path) == len(nums):
            result.append(path[:])
        set_ = set()
        for i in range(len(nums)):
            if nums[i] in set_ or used[i]:
                continue
            path.append(nums[i])
            used[i] = True
            set_.add(nums[i])
            self.backtracking(nums,used,path,result)
            used[i] = False
            path.pop()
    def permuteUnique(self, nums: List[int]) -> List[List[int]]:
        result = []
        used = [False] * len(nums)
        self.backtracking(nums,used,[],result)
        return result