Mission

491. Increment Subsequence

Given an array of integers, numbers, find and return all the distinct incrementing subsequences in the array, with at least two elements in the incrementing subsequence. You can return the answers in any order.
An array may contain duplicate elements, and if two integers are equal, it can also be considered a special case of an increasing sequence.

Thinking

According to the meaning of the question, because the required subsequence is related to the order, so the original array cannot be sorted, then the previous used method and i > start method cannot be used to duplicate, because both methods need to sort the original array. Consider horizontal pruning with set here.

• Since vertical pruning is incremental, vertical pruning removes non-conformities by comparing the current value nums[i] with its parent value path[-1].
• Lateral pruning local variable set to add new elements, in the same level of the loop, if there are already the same elements, then the new node pruning, because it is a local variable, do not need explicit backtracking.
  Overall logic: Take one node, next time in the rest of the sequence, recursively, and then collect based on at least two elements of the subsequence.

class Solution:
    def __init__(self) -> None:
        self.path = []
        self.paths = []
    def findSubsequences(self, nums: List[int]) -> List[List[int]]:
        self.dfs(nums,0)
        return self.paths
    def dfs(self,nums,start):
        if len(self.path)>1:
            self.paths.append(self.path[:])

        size = len(nums)
        uset = set()
        for i in range(start,size):
            if (self.path and nums[i]< self.path[-1]): #Prune according to condition when digging (the value of new node is less than the value of previous node)
                continue
            if nums[i] in uset:
                continue

            uset.add(nums[i])    #Lateral pruning (de-duplication) Because the solution is an ordered subsequence, it cannot be sorted and then used i > start to de-duplicate as before, and use local variable set to de-duplicate, and because it is a local variable, there is no need to explicitly backtrack. The elements in set represent the used elements of the layer.
            self.path.append(nums[i])
            self.dfs(nums,i+1)
            self.path.pop()

46. full permutation

Given an array nums that contains no duplicate digits, return all possible permutations of it. You can return the answers in any order.

Thinking

Since all permutations select a number, other numbers can be taken, so it is not used to recursively drive. There are two ways to think about it.

1. Consider using the used array to represent list elements that have been used. You can take unused list elements each time until a path has processed all elements. This condition can be expressed by len(path)==len(numbers).
2. Consider using the unKnownFirst sentinel drive method to represent the sentinel that currently processes the element. It divides the original list into two parts.[0,unKnownFirst) represents the selected part.[unKnownFirst, size) represents the selected part. As the recursion proceeds, unKnownFirst eventually equals size, that is, the selection of a path is completed.

#Method 1 used array
class Solution:
    def __init__(self) -> None:
        self.path = []
        self.paths = []

    def permute(self, nums: List[int]) -> List[List[int]]:
        used = [False] * len(nums)
        self.dfs(nums,used)
        return self.paths
    def dfs(self,nums,used):
        if len(self.path) == len(nums):
            self.paths.append(self.path[:])
            return 

        for i in range(0,len(nums)):
            if used[i]:
                continue

            used[i] = True
            self.path.append(nums[i])
            self.dfs(nums,used)
            self.path.pop()
            used[i] = False

# 方法2 unKnownFirst哨兵
class Solution:
    def __init__(self) -> None:
        self.path = []
        self.paths = []

    def permute(self, nums: List[int]) -> List[List[int]]:
        self.dfs(nums,0)
        return self.paths
    def dfs(self,nums,unKnowFirst): # unKnowFirst 为当前第unKnowFirst的位置的值选哪个
        if unKnowFirst == len(nums):
            self.paths.append(self.path[:])
            return 

        for i in range(unKnowFirst,len(nums)):
            nums[i],nums[unKnowFirst] = nums[unKnowFirst],nums[i]
            self.path.append(nums[unKnowFirst])
            self.dfs(nums,unKnowFirst+1)
            self.path.pop()
            nums[i],nums[unKnowFirst] = nums[unKnowFirst],nums[i]

47.全排列II

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

思路

由于包含重复元素，且需要返回不重复的全排列，所以需要去重。想到了之前组合中的去重方法，使用used数组进行横向剪枝。

class Solution:
    def __init__(self) -> None:
        self.path = []
        self.paths = []
        self.used = []
    def permuteUnique(self, nums: List[int]) -> List[List[int]]:
        self.used = [False] * len(nums)
        nums.sort()
        self.dfs(nums)
        return self.paths
    def dfs(self,nums):
        if un == len(nums):
            self.paths.append(self.path[:])
            return 

        for i in range(0,len(nums)):
            if self.used[i]:
                continue
            if i> 0 and nums[i] == nums[i-1] and self.used[i-1] == False:
                continue
            self.used[i] = True
            self.path.append(nums[i])
            self.dfs(nums)
            self.path.pop()
            self.used[i] =False

心得体会

暴力递归类的题目目前做过的类型如下：
组合： start 驱动，考虑进入下一层的时候start需要为多少，如下一个数在后续元素中选取。终止条件（收集信息）是到达需求的数量k，此时即为叶子节点，此时收集一条路径的信息，used数组或者i>start条件进行横向去重，注意去重之前要排序
子集： start 驱动，考虑进入下一层的时候start需要为多少，如下一个数在后续元素中选取,终止条件是任意节点，都将它包含的路径加入到最终结果中。递增子序列是一个类子集问题，由于不能排序所以横向剪枝采用局部变量set。
分割： 对比其他的问题相对抽象，start驱动，考虑进入下一层的时候start需要为多少，如下一个分割在后续索引中选取，终止条件为分割索引到达size。[start,i]一般表示该次分割的范围区间。
排列：used驱动，每次只要没选过都可以选。或者unKnownFirst驱动，每次选取的放在unKnownFirst，然后unKnownFirst+1驱动dfs。终止条件为排列完成，len(path)len(nums) 或者 unKnownFirstlen(nums) 去重方面，同前面问题使用used数组，注意去重前需要排序。

剩余题目有时间刷：
332.重新安排行程 暂时看不懂题目
51. N皇后 感觉比较简单
37. 解数独 还没看