代码随想录算法训练营第二十九天 | LeetCode491 递增子序列、LeetCode46 全排列、LeetCode47 全排列Ⅱ

今日任务：

LeetCode491 递增子序列
LeetCode46 全排列
LeetCode47 全排列Ⅱ

资料来源：

1 LeetCode491 递增子序列

题目

给你一个整数数组 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]]

提示：

1 <= nums.length <= 15
-100 <= nums[i] <= 100

还是回溯的思路，但是这次去重不能排序了，因为这次是让求序列，如果排序后会失去元素的有序性。而且这次不是树层查重，是递归查重。

（嫖一张思路图）

python
from typing import List

class Solution:
    def __init__(self):
        self.result = []
        self.nums = []
        self.path = []

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

    def back_tracking(self, start_index: int):
        if len(self.path) >= 2:
            self.result.append(self.path.copy())
        number_used = [0] * 201
        for i in range(start_index, len(self.nums)):
            if (len(self.path) > 0 and self.nums[i] < self.path[-1]) or number_used[self.nums[i] + 100] == 1:
                continue
            self.path.append(self.nums[i])
            number_used[self.nums[i] + 100] = 1
            self.back_tracking(i + 1)
            self.path.pop()

提示

注意这两种写法的区别：

python
if len(self.path) > 0:
    if self.nums[i] < self.path[-1] or number_used[self.nums[i] + 100] == 1:
        continue

python
if (len(self.path) > 0 and self.nums[i] < self.path[-1]) or number_used[self.nums[i] + 100] == 1:
    continue

第一种写法是错误的，它会导致某些len(self.path) == 0的情况原本应该被递归查重的条件number_used[self.nums[i] + 100] == 1排除掉，结果反而没有被排除，从而导致这个用例无法通过：


> 2024/04/03 15:11:09	
Wrong Answer:
	input:[1,2,3,4,5,6,7,8,9,10,1,1,1,1,1]
	Output:[[1,2],[1,2,3],[1,2,3,4],[1,2,3,4,5],[1,2,3,4,5,6],[1,2,3,4,5,6,7],[1,2,3,4,5,6,7,8],[1,2,3,4,5,6,7,8,9],[1,2,3,4,5,6,7,8,9,10],[1,2,3,4,5,6,7,8,10],[1,2,3,4,5,6,7,9],[1,2,3,4,5,6,7,9,10],[1,2,3,4,5,6,7,10],[1,2,3,4,5,6,8],[1,2,3,4,5,6,8,9],[1,2,3,4,5,6,8,9,10],[1,2,3,4,5,6,8,10],[1,2,3,4,5,6,9],[1,2,3,4,5,6,9,10],[1,2,3,4,5,6,10],[1,2,3,4,5,7],[1,2,3,4,5,7,8],[1,2,3,4,5,7,8,9],[1,2,3,4,5,7,8,9,10],[1,2,3,4,5,7,8,10],[1,2,3,4,5,7,9],[1,2,3,4,5,7,9,10],[1,2,3,4,5,7,10],[1,2,3,4,5,8],[1,2,3,4,5,8,9],[1,2,3,4,5,8,9,10],[1,2,3,4,5,8,10],[1,2,3,4,5,9],[1,2,3,4,5,9,10],[1,2,3,4,5,10],[1,2,3,4,6],[1,2,3,4,6,7],[1,2,3,4,6,7,8],[1,2,3,4,6,7,8,9],[1,2,3,4,6,7,8,9,10],[1,2,3,4,6,7,8,10],[1,2,3,4,6,7,9],[1,2,3,4,6,7,9,10],[1,2,3,4,6,7,10],[1,2,3,4,6,8],[1,2,3,4,6,8,9],[1,2,3,4,6,8,9,10],[1,2,3,4,6,8,10],[1,2,3,4,6,9],[1,2,3,4,6,9,10],[1,2,3,4,6,10],[1,2,3,4,7],[1,2,3,4,7,8],[1,2,3,4,7,8,9],[1,2,3,4,7,8,9,10],[1,2,3,4,7,8,10],[1,2,3,4,7,9],[1,2,3,4,7,9,10],[1,2,3,4,7,10],[1,2,3,4,8],[1,2,3,4,8,9],[1,2,3,4,8,9,10],[1,2,3,4,8,10],[1,2,3,4,9],[1,2,3,4,9,10],[1,2,3,4,10],[1,2,3,5],[1,2,3,5,6],[1,2,3,5,6,7],[1,2,3,5,6,7,8],[1,2,3,5,6,7,8,9],[1,2,3,5,6,7,8,9,10],[1,2,3,5,6,7,8,10],[1,2,3,5,6,7,9],[1,2,3,5,6,7,9,10],[1,2,3,5,6,7,10],[1,2,3,5,6,8],[1,2,3,5,6,8,9],[1,2,3,5,6,8,9,10],[1,2,3,5,6,8,10],[1,2,3,5,6,9],[1,2,3,5,6,9,10],[1,2,3,5,6,10],[1,2,3,5,7],[1,2,3,5,7,8],[1,2,3,5,7,8,9],[1,2,3,5,7,8,9,10],[1,2,3,5,7,8,10],[1,2,3,5,7,9],[1,2,3,5,7,9,10],[1,2,3,5,7,10],[1,2,3,5,8],[1,2,3,5,8,9],[1,2,3,5,8,9,10],[1,2,3,5,8,10],[1,2,3,5,9],[1,2,3,5,9,10],[1,2,3,5,10],[1,2,3,6],[1,2,3,6,7],[1,2,3,6,7,8],[1,2,3,6,7,8,9],[1,2,3,6,7,8,9,10],[1,2,3,6,7,8,10],[1,2,3,6,7,9],[1,2,3,6,7,9,10],[1,2,3,6,7,10],[1,2,3,6,8],[1,2,3,6,8,9],[1,2,3,6,8,9,10],[1,2,3,6,8,10],[1,2,3,6,9],[1,2,3,6,9,10],[1,2,3,6,10],[1,2,3,7],[1,2,3,7,8],[1,2,3,7,8,9],[1,2,3,7,8,9,10],[1,2,3,7,8,10],[1,2,3,7,9],[1,2,3,7,9,10],[1,2,3,7,10],[1,2,3,8],[1,2,3,8,9],[1,2,3,8,9,10],[1,2,3,8,10],[1,2,3,9],[1,2,3,9,10],[1,2,3,10],[1,2,4],[1,2,4,5],[1,2,4,5,6],[1,2,4,5,6,7],[1,2,4,5,6,7,8],[1,2,4,5,6,7,8,9],[1,2,4,5,6,7,8,9,10],[1,2,4,5,6,7,8,10],[1,2,4,5,6,7,9],[1,2,4,5,6,7,9,10],[1,2,4,5,6,7,10],[1,2,4,5,6,8],[1,2,4,5,6,8,9],[1,2,4,5,6,8,9,10],[1,2,4,5,6,8,10],[1,2,4,5,6,9],[1,2,4,5,6,9,10],[1,2,4,5,6,10],[1,2,4,5,7],[1,2,4,5,7,8],[1,2,4,5,7,8,9],[1,2,4,5,7,8,9,10],[1,2,4,5,7,8,10],[1,2,4,5,7,9],[1,2,4,5,7,9,10],[1,2,4,5,7,10],[1,2,4,5,8],[1,2,4,5,8,9],[1,2,4,5,8,9,10],[1,2,4,5,8,10],[1,2,4,5,9],[1,2,4,5,9,10],[1,2,4,5,10],[1,2,4,6],[1,2,4,6,7],[1,2,4,6,7,8],[1,2,4,6,7,8,9],[1,2,4,6,7,8,9,10],[1,2,4,6,7,8,10],[1,2,4,6,7,9],[1,2,4,6,7,9,10],[1,2,4,6,7,10],[1,2,4,6,8],[1,2,4,6,8,9],[1,2,4,6,8,9,10],[1,2,4,6,8,10],[1,2,4,6,9],[1,2,4,6,9,10],[1,2,4,6,10],[1,2,4,7],[1,2,4,7,8],[1,2,4,7,8,9],[1,2,4,7,8,9,10],[1,2,4,7,8,10],[1,2,4,7,9],[1,2,4,7,9,10],[1,2,4,7,10],[1,2,4,8],[1,2,4,8,9],[1,2,4,8,9,10],[1,2,4,8,10],[1,2,4,9],[1,2,4,9,10],[1,2,4,10],[1,2,5],[1,2,5,6],[1,2,5,6,7],[1,2,5,6,7,8],[1,2,5,6,7,8,9],[1,2,5,6,7,8,9,10],[1,2,5,6,7,8,10],[1,2,5,6,7,9],[1,2,5,6,7,9,10],[1,2,5,6,7,10],[1,2,5,6,8],[1,2,5,6,8,9],[1,2,5,6,8,9,10],[1,2,5,6,8,10],[1,2,5,6,9],[1,2,5,6,9,10],[1,2,5,6,10],[1,2,5,7],[1,2,5,7,8],[1,2,5,7,8,9],[1,2,5,7,8,9,10],[1,2,5,7,8,10],[1,2,5,7,9],[1,2,5,7,9,10],[1,2,5,7,10],[1,2,5,8],[1,2,5,8,9],[1,2,5,8,9,10],[1,2,5,8,10],[1,2,5,9],[1,2,5,9,10],[1,2,5,10],[1,2,6],[1,2,6,7],[1,2,6,7,8],[1,2,6,7,8,9],[1,2,6,7,8,9,10],[1,2,6,7,8,10],[1,2,6,7,9],[1,2,6,7,9,10],[1,2,6,7,10],[1,2,6,8],[1,2,6,8,9],[1,2,6,8,9,10],[1,2,6,8,10],[1,2,6,9],[1,2,6,9,10],[1,2,6,10],[1,2,7],[1,2,7,8],[1,2,7,8,9],[1,2,7,8,9,10],[1,2,7,8,10],[1,2,7,9],[1,2,7,9,10],[1,2,7,10],[1,2,8],[1,2,8,9],[1,2,8,9,10],[1,2,8,10],[1,2,9],[1,2,9,10],[1,2,10],[1,3],[1,3,4],[1,3,4,5],[1,3,4,5,6],[1,3,4,5,6,7],[1,3,4,5,6,7,8],[1,3,4,5,6,7,8,9],[1,3,4,5,6,7,8,9,10],[1,3,4,5,6,7,8,10],[1,3,4,5,6,7,9],[1,3,4,5,6,7,9,10],[1,3,4,5,6,7,10],[1,3,4,5,6,8],[1,3,4,5,6,8,9],[1,3,4,5,6,8,9,10],[1,3,4,5,6,8,10],[1,3,4,5,6,9],[1,3,4,5,6,9,10],[1,3,4,5,6,10],[1,3,4,5,7],[1,3,4,5,7,8],[1,3,4,5,7,8,9],[1,3,4,5,7,8,9,10],[1,3,4,5,7,8,10],[1,3,4,5,7,9],[1,3,4,5,7,9,10],[1,3,4,5,7,10],[1,3,4,5,8],[1,3,4,5,8,9],[1,3,4,5,8,9,10],[1,3,4,5,8,10],[1,3,4,5,9],[1,3,4,5,9,10],[1,3,4,5,10],[1,3,4,6],[1,3,4,6,7],[1,3,4,6,7,8],[1,3,4,6,7,8,9],[1,3,4,6,7,8,9,10],[1,3,4,6,7,8,10],[1,3,4,6,7,9],[1,3,4,6,7,9,10],[1,3,4,6,7,10],[1,3,4,6,8],[1,3,4,6,8,9],[1,3,4,6,8,9,10],[1,3,4,6,8,10],[1,3,4,6,9],[1,3,4,6,9,10],[1,3,4,6,10],[1,3,4,7],[1,3,4,7,8],[1,3,4,7,8,9],[1,3,4,7,8,9,10],[1,3,4,7,8,10],[1,3,4,7,9],[1,3,4,7,9,10],[1,3,4,7,10],[1,3,4,8],[1,3,4,8,9],[1,3,4,8,9,10],[1,3,4,8,10],[1,3,4,9],[1,3,4,9,10],[1,3,4,10],[1,3,5],[1,3,5,6],[1,3,5,6,7],[1,3,5,6,7,8],[1,3,5,6,7,8,9],[1,3,5,6,7,8,9,10],[1,3,5,6,7,8,10],[1,3,5,6,7,9],[1,3,5,6,7,9,10],[1,3,5,6,7,10],[1,3,5,6,8],[1,3,5,6,8,9],[1,3,5,6,8,9,10],[1,3,5,6,8,10],[1,3,5,6,9],[1,3,5,6,9,10],[1,3,5,6,10],[1,3,5,7],[1,3,5,7,8],[1,3,5,7,8,9],[1,3,5,7,8,9,10],[1,3,5,7,8,10],[1,3,5,7,9],[1,3,5,7,9,10],[1,3,5,7,10],[1,3,5,8],[1,3,5,8,9],[1,3,5,8,9,10],[1,3,5,8,10],[1,3,5,9],[1,3,5,9,10],[1,3,5,10],[1,3,6],[1,3,6,7],[1,3,6,7,8],[1,3,6,7,8,9],[1,3,6,7,8,9,10],[1,3,6,7,8,10],[1,3,6,7,9],[1,3,6,7,9,10],[1,3,6,7,10],[1,3,6,8],[1,3,6,8,9],[1,3,6,8,9,10],[1,3,6,8,10],[1,3,6,9],[1,3,6,9,10],[1,3,6,10],[1,3,7],[1,3,7,8],[1,3,7,8,9],[1,3,7,8,9,10],[1,3,7,8,10],[1,3,7,9],[1,3,7,9,10],[1,3,7,10],[1,3,8],[1,3,8,9],[1,3,8,9,10],[1,3,8,10],[1,3,9],[1,3,9,10],[1,3,10],[1,4],[1,4,5],[1,4,5,6],[1,4,5,6,7],[1,4,5,6,7,8],[1,4,5,6,7,8,9],[1,4,5,6,7,8,9,10],[1,4,5,6,7,8,10],[1,4,5,6,7,9],[1,4,5,6,7,9,10],[1,4,5,6,7,10],[1,4,5,6,8],[1,4,5,6,8,9],[1,4,5,6,8,9,10],[1,4,5,6,8,10],[1,4,5,6,9],[1,4,5,6,9,10],[1,4,5,6,10],[1,4,5,7],[1,4,5,7,8],[1,4,5,7,8,9],[1,4,5,7,8,9,10],[1,4,5,7,8,10],[1,4,5,7,9],[1,4,5,7,9,10],[1,4,5,7,10],[1,4,5,8],[1,4,5,8,9],[1,4,5,8,9,10],[1,4,5,8,10],[1,4,5,9],[1,4,5,9,10],[1,4,5,10],[1,4,6],[1,4,6,7],[1,4,6,7,8],[1,4,6,7,8,9],[1,4,6,7,8,9,10],[1,4,6,7,8,10],[1,4,6,7,9],[1,4,6,7,9,10],[1,4,6,7,10],[1,4,6,8],[1,4,6,8,9],[1,4,6,8,9,10],[1,4,6,8,10],[1,4,6,9],[1,4,6,9,10],[1,4,6,10],[1,4,7],[1,4,7,8],[1,4,7,8,9],[1,4,7,8,9,10],[1,4,7,8,10],[1,4,7,9],[1,4,7,9,10],[1,4,7,10],[1,4,8],[1,4,8,9],[1,4,8,9,10],[1,4,8,10],[1,4,9],[1,4,9,10],[1,4,10],[1,5],[1,5,6],[1,5,6,7],[1,5,6,7,8],[1,5,6,7,8,9],[1,5,6,7,8,9,10],[1,5,6,7,8,10],[1,5,6,7,9],[1,5,6,7,9,10],[1,5,6,7,10],[1,5,6,8],[1,5,6,8,9],[1,5,6,8,9,10],[1,5,6,8,10],[1,5,6,9],[1,5,6,9,10],[1,5,6,10],[1,5,7],[1,5,7,8],[1,5,7,8,9],[1,5,7,8,9,10],[1,5,7,8,10],[1,5,7,9],[1,5,7,9,10],[1,5,7,10],[1,5,8],[1,5,8,9],[1,5,8,9,10],[1,5,8,10],[1,5,9],[1,5,9,10],[1,5,10],[1,6],[1,6,7],[1,6,7,8],[1,6,7,8,9],[1,6,7,8,9,10],[1,6,7,8,10],[1,6,7,9],[1,6,7,9,10],[1,6,7,10],[1,6,8],[1,6,8,9],[1,6,8,9,10],[1,6,8,10],[1,6,9],[1,6,9,10],[1,6,10],[1,7],[1,7,8],[1,7,8,9],[1,7,8,9,10],[1,7,8,10],[1,7,9],[1,7,9,10],[1,7,10],[1,8],[1,8,9],[1,8,9,10],[1,8,10],[1,9],[1,9,10],[1,10],[1,1],[1,1,1],[1,1,1,1],[1,1,1,1,1],[1,1,1,1,1,1],[2,3],[2,3,4],[2,3,4,5],[2,3,4,5,6],[2,3,4,5,6,7],[2,3,4,5,6,7,8],[2,3,4,5,6,7,8,9],[2,3,4,5,6,7,8,9,10],[2,3,4,5,6,7,8,10],[2,3,4,5,6,7,9],[2,3,4,5,6,7,9,10],[2,3,4,5,6,7,10],[2,3,4,5,6,8],[2,3,4,5,6,8,9],[2,3,4,5,6,8,9,10],[2,3,4,5,6,8,10],[2,3,4,5,6,9],[2,3,4,5,6,9,10],[2,3,4,5,6,10],[2,3,4,5,7],[2,3,4,5,7,8],[2,3,4,5,7,8,9],[2,3,4,5,7,8,9,10],[2,3,4,5,7,8,10],[2,3,4,5,7,9],[2,3,4,5,7,9,10],[2,3,4,5,7,10],[2,3,4,5,8],[2,3,4,5,8,9],[2,3,4,5,8,9,10],[2,3,4,5,8,10],[2,3,4,5,9],[2,3,4,5,9,10],[2,3,4,5,10],[2,3,4,6],[2,3,4,6,7],[2,3,4,6,7,8],[2,3,4,6,7,8,9],[2,3,4,6,7,8,9,10],[2,3,4,6,7,8,10],[2,3,4,6,7,9],[2,3,4,6,7,9,10],[2,3,4,6,7,10],[2,3,4,6,8],[2,3,4,6,8,9],[2,3,4,6,8,9,10],[2,3,4,6,8,10],[2,3,4,6,9],[2,3,4,6,9,10],[2,3,4,6,10],[2,3,4,7],[2,3,4,7,8],[2,3,4,7,8,9],[2,3,4,7,8,9,10],[2,3,4,7,8,10],[2,3,4,7,9],[2,3,4,7,9,10],[2,3,4,7,10],[2,3,4,8],[2,3,4,8,9],[2,3,4,8,9,10],[2,3,4,8,10],[2,3,4,9],[2,3,4,9,10],[2,3,4,10],[2,3,5],[2,3,5,6],[2,3,5,6,7],[2,3,5,6,7,8],[2,3,5,6,7,8,9],[2,3,5,6,7,8,9,10],[2,3,5,6,7,8,10],[2,3,5,6,7,9],[2,3,5,6,7,9,10],[2,3,5,6,7,10],[2,3,5,6,8],[2,3,5,6,8,9],[2,3,5,6,8,9,10],[2,3,5,6,8,10],[2,3,5,6,9],[2,3,5,6,9,10],[2,3,5,6,10],[2,3,5,7],[2,3,5,7,8],[2,3,5,7,8,9],[2,3,5,7,8,9,10],[2,3,5,7,8,10],[2,3,5,7,9],[2,3,5,7,9,10],[2,3,5,7,10],[2,3,5,8],[2,3,5,8,9],[2,3,5,8,9,10],[2,3,5,8,10],[2,3,5,9],[2,3,5,9,10],[2,3,5,10],[2,3,6],[2,3,6,7],[2,3,6,7,8],[2,3,6,7,8,9],[2,3,6,7,8,9,10],[2,3,6,7,8,10],[2,3,6,7,9],[2,3,6,7,9,10],[2,3,6,7,10],[2,3,6,8],[2,3,6,8,9],[2,3,6,8,9,10],[2,3,6,8,10],[2,3,6,9],[2,3,6,9,10],[2,3,6,10],[2,3,7],[2,3,7,8],[2,3,7,8,9],[2,3,7,8,9,10],[2,3,7,8,10],[2,3,7,9],[2,3,7,9,10],[2,3,7,10],[2,3,8],[2,3,8,9],[2,3,8,9,10],[2,3,8,10],[2,3,9],[2,3,9,10],[2,3,10],[2,4],[2,4,5],[2,4,5,6],[2,4,5,6,7],[2,4,5,6,7,8],[2,4,5,6,7,8,9],[2,4,5,6,7,8,9,10],[2,4,5,6,7,8,10],[2,4,5,6,7,9],[2,4,5,6,7,9,10],[2,4,5,6,7,10],[2,4,5,6,8],[2,4,5,6,8,9],[2,4,5,6,8,9,10],[2,4,5,6,8,10],[2,4,5,6,9],[2,4,5,6,9,10],[2,4,5,6,10],[2,4,5,7],[2,4,5,7,8],[2,4,5,7,8,9],[2,4,5,7,8,9,10],[2,4,5,7,8,10],[2,4,5,7,9],[2,4,5,7,9,10],[2,4,5,7,10],[2,4,5,8],[2,4,5,8,9],[2,4,5,8,9,10],[2,4,5,8,10],[2,4,5,9],[2,4,5,9,10],[2,4,5,10],[2,4,6],[2,4,6,7],[2,4,6,7,8],[2,4,6,7,8,9],[2,4,6,7,8,9,10],[2,4,6,7,8,10],[2,4,6,7,9],[2,4,6,7,9,10],[2,4,6,7,10],[2,4,6,8],[2,4,6,8,9],[2,4,6,8,9,10],[2,4,6,8,10],[2,4,6,9],[2,4,6,9,10],[2,4,6,10],[2,4,7],[2,4,7,8],[2,4,7,8,9],[2,4,7,8,9,10],[2,4,7,8,10],[2,4,7,9],[2,4,7,9,10],[2,4,7,10],[2,4,8],[2,4,8,9],[2,4,8,9,10],[2,4,8,10],[2,4,9],[2,4,9,10],[2,4,10],[2,5],[2,5,6],[2,5,6,7],[2,5,6,7,8],[2,5,6,7,8,9],[2,5,6,7,8,9,10],[2,5,6,7,8,10],[2,5,6,7,9],[2,5,6,7,9,10],[2,5,6,7,10],[2,5,6,8],[2,5,6,8,9],[2,5,6,8,9,10],[2,5,6,8,10],[2,5,6,9],[2,5,6,9,10],[2,5,6,10],[2,5,7],[2,5,7,8],[2,5,7,8,9],[2,5,7,8,9,10],[2,5,7,8,10],[2,5,7,9],[2,5,7,9,10],[2,5,7,10],[2,5,8],[2,5,8,9],[2,5,8,9,10],[2,5,8,10],[2,5,9],[2,5,9,10],[2,5,10],[2,6],[2,6,7],[2,6,7,8],[2,6,7,8,9],[2,6,7,8,9,10],[2,6,7,8,10],[2,6,7,9],[2,6,7,9,10],[2,6,7,10],[2,6,8],[2,6,8,9],[2,6,8,9,10],[2,6,8,10],[2,6,9],[2,6,9,10],[2,6,10],[2,7],[2,7,8],[2,7,8,9],[2,7,8,9,10],[2,7,8,10],[2,7,9],[2,7,9,10],[2,7,10],[2,8],[2,8,9],[2,8,9,10],[2,8,10],[2,9],[2,9,10],[2,10],[3,4],[3,4,5],[3,4,5,6],[3,4,5,6,7],[3,4,5,6,7,8],[3,4,5,6,7,8,9],[3,4,5,6,7,8,9,10],[3,4,5,6,7,8,10],[3,4,5,6,7,9],[3,4,5,6,7,9,10],[3,4,5,6,7,10],[3,4,5,6,8],[3,4,5,6,8,9],[3,4,5,6,8,9,10],[3,4,5,6,8,10],[3,4,5,6,9],[3,4,5,6,9,10],[3,4,5,6,10],[3,4,5,7],[3,4,5,7,8],[3,4,5,7,8,9],[3,4,5,7,8,9,10],[3,4,5,7,8,10],[3,4,5,7,9],[3,4,5,7,9,10],[3,4,5,7,10],[3,4,5,8],[3,4,5,8,9],[3,4,5,8,9,10],[3,4,5,8,10],[3,4,5,9],[3,4,5,9,10],[3,4,5,10],[3,4,6],[3,4,6,7],[3,4,6,7,8],[3,4,6,7,8,9],[3,4,6,7,8,9,10],[3,4,6,7,8,10],[3,4,6,7,9],[3,4,6,7,9,10],[3,4,6,7,10],[3,4,6,8],[3,4,6,8,9],[3,4,6,8,9,10],[3,4,6,8,10],[3,4,6,9],[3,4,6,9,10],[3,4,6,10],[3,4,7],[3,4,7,8],[3,4,7,8,9],[3,4,7,8,9,10],[3,4,7,8,10],[3,4,7,9],[3,4,7,9,10],[3,4,7,10],[3,4,8],[3,4,8,9],[3,4,8,9,10],[3,4,8,10],[3,4,9],[3,4,9,10],[3,4,10],[3,5],[3,5,6],[3,5,6,7],[3,5,6,7,8],[3,5,6,7,8,9],[3,5,6,7,8,9,10],[3,5,6,7,8,10],[3,5,6,7,9],[3,5,6,7,9,10],[3,5,6,7,10],[3,5,6,8],[3,5,6,8,9],[3,5,6,8,9,10],[3,5,6,8,10],[3,5,6,9],[3,5,6,9,10],[3,5,6,10],[3,5,7],[3,5,7,8],[3,5,7,8,9],[3,5,7,8,9,10],[3,5,7,8,10],[3,5,7,9],[3,5,7,9,10],[3,5,7,10],[3,5,8],[3,5,8,9],[3,5,8,9,10],[3,5,8,10],[3,5,9],[3,5,9,10],[3,5,10],[3,6],[3,6,7],[3,6,7,8],[3,6,7,8,9],[3,6,7,8,9,10],[3,6,7,8,10],[3,6,7,9],[3,6,7,9,10],[3,6,7,10],[3,6,8],[3,6,8,9],[3,6,8,9,10],[3,6,8,10],[3,6,9],[3,6,9,10],[3,6,10],[3,7],[3,7,8],[3,7,8,9],[3,7,8,9,10],[3,7,8,10],[3,7,9],[3,7,9,10],[3,7,10],[3,8],[3,8,9],[3,8,9,10],[3,8,10],[3,9],[3,9,10],[3,10],[4,5],[4,5,6],[4,5,6,7],[4,5,6,7,8],[4,5,6,7,8,9],[4,5,6,7,8,9,10],[4,5,6,7,8,10],[4,5,6,7,9],[4,5,6,7,9,10],[4,5,6,7,10],[4,5,6,8],[4,5,6,8,9],[4,5,6,8,9,10],[4,5,6,8,10],[4,5,6,9],[4,5,6,9,10],[4,5,6,10],[4,5,7],[4,5,7,8],[4,5,7,8,9],[4,5,7,8,9,10],[4,5,7,8,10],[4,5,7,9],[4,5,7,9,10],[4,5,7,10],[4,5,8],[4,5,8,9],[4,5,8,9,10],[4,5,8,10],[4,5,9],[4,5,9,10],[4,5,10],[4,6],[4,6,7],[4,6,7,8],[4,6,7,8,9],[4,6,7,8,9,10],[4,6,7,8,10],[4,6,7,9],[4,6,7,9,10],[4,6,7,10],[4,6,8],[4,6,8,9],[4,6,8,9,10],[4,6,8,10],[4,6,9],[4,6,9,10],[4,6,10],[4,7],[4,7,8],[4,7,8,9],[4,7,8,9,10],[4,7,8,10],[4,7,9],[4,7,9,10],[4,7,10],[4,8],[4,8,9],[4,8,9,10],[4,8,10],[4,9],[4,9,10],[4,10],[5,6],[5,6,7],[5,6,7,8],[5,6,7,8,9],[5,6,7,8,9,10],[5,6,7,8,10],[5,6,7,9],[5,6,7,9,10],[5,6,7,10],[5,6,8],[5,6,8,9],[5,6,8,9,10],[5,6,8,10],[5,6,9],[5,6,9,10],[5,6,10],[5,7],[5,7,8],[5,7,8,9],[5,7,8,9,10],[5,7,8,10],[5,7,9],[5,7,9,10],[5,7,10],[5,8],[5,8,9],[5,8,9,10],[5,8,10],[5,9],[5,9,10],[5,10],[6,7],[6,7,8],[6,7,8,9],[6,7,8,9,10],[6,7,8,10],[6,7,9],[6,7,9,10],[6,7,10],[6,8],[6,8,9],[6,8,9,10],[6,8,10],[6,9],[6,9,10],[6,10],[7,8],[7,8,9],[7,8,9,10],[7,8,10],[7,9],[7,9,10],[7,10],[8,9],[8,9,10],[8,10],[9,10],[1,1],[1,1,1],[1,1,1,1],[1,1,1,1,1],[1,1],[1,1,1],[1,1,1,1],[1,1],[1,1,1],[1,1]]
	Expected:[[1,2],[1,2,3],[1,2,3,4],[1,2,3,4,5],[1,2,3,4,5,6],[1,2,3,4,5,6,7],[1,2,3,4,5,6,7,8],[1,2,3,4,5,6,7,8,9],[1,2,3,4,5,6,7,8,9,10],[1,2,3,4,5,6,7,8,10],[1,2,3,4,5,6,7,9],[1,2,3,4,5,6,7,9,10],[1,2,3,4,5,6,7,10],[1,2,3,4,5,6,8],[1,2,3,4,5,6,8,9],[1,2,3,4,5,6,8,9,10],[1,2,3,4,5,6,8,10],[1,2,3,4,5,6,9],[1,2,3,4,5,6,9,10],[1,2,3,4,5,6,10],[1,2,3,4,5,7],[1,2,3,4,5,7,8],[1,2,3,4,5,7,8,9],[1,2,3,4,5,7,8,9,10],[1,2,3,4,5,7,8,10],[1,2,3,4,5,7,9],[1,2,3,4,5,7,9,10],[1,2,3,4,5,7,10],[1,2,3,4,5,8],[1,2,3,4,5,8,9],[1,2,3,4,5,8,9,10],[1,2,3,4,5,8,10],[1,2,3,4,5,9],[1,2,3,4,5,9,10],[1,2,3,4,5,10],[1,2,3,4,6],[1,2,3,4,6,7],[1,2,3,4,6,7,8],[1,2,3,4,6,7,8,9],[1,2,3,4,6,7,8,9,10],[1,2,3,4,6,7,8,10],[1,2,3,4,6,7,9],[1,2,3,4,6,7,9,10],[1,2,3,4,6,7,10],[1,2,3,4,6,8],[1,2,3,4,6,8,9],[1,2,3,4,6,8,9,10],[1,2,3,4,6,8,10],[1,2,3,4,6,9],[1,2,3,4,6,9,10],[1,2,3,4,6,10],[1,2,3,4,7],[1,2,3,4,7,8],[1,2,3,4,7,8,9],[1,2,3,4,7,8,9,10],[1,2,3,4,7,8,10],[1,2,3,4,7,9],[1,2,3,4,7,9,10],[1,2,3,4,7,10],[1,2,3,4,8],[1,2,3,4,8,9],[1,2,3,4,8,9,10],[1,2,3,4,8,10],[1,2,3,4,9],[1,2,3,4,9,10],[1,2,3,4,10],[1,2,3,5],[1,2,3,5,6],[1,2,3,5,6,7],[1,2,3,5,6,7,8],[1,2,3,5,6,7,8,9],[1,2,3,5,6,7,8,9,10],[1,2,3,5,6,7,8,10],[1,2,3,5,6,7,9],[1,2,3,5,6,7,9,10],[1,2,3,5,6,7,10],[1,2,3,5,6,8],[1,2,3,5,6,8,9],[1,2,3,5,6,8,9,10],[1,2,3,5,6,8,10],[1,2,3,5,6,9],[1,2,3,5,6,9,10],[1,2,3,5,6,10],[1,2,3,5,7],[1,2,3,5,7,8],[1,2,3,5,7,8,9],[1,2,3,5,7,8,9,10],[1,2,3,5,7,8,10],[1,2,3,5,7,9],[1,2,3,5,7,9,10],[1,2,3,5,7,10],[1,2,3,5,8],[1,2,3,5,8,9],[1,2,3,5,8,9,10],[1,2,3,5,8,10],[1,2,3,5,9],[1,2,3,5,9,10],[1,2,3,5,10],[1,2,3,6],[1,2,3,6,7],[1,2,3,6,7,8],[1,2,3,6,7,8,9],[1,2,3,6,7,8,9,10],[1,2,3,6,7,8,10],[1,2,3,6,7,9],[1,2,3,6,7,9,10],[1,2,3,6,7,10],[1,2,3,6,8],[1,2,3,6,8,9],[1,2,3,6,8,9,10],[1,2,3,6,8,10],[1,2,3,6,9],[1,2,3,6,9,10],[1,2,3,6,10],[1,2,3,7],[1,2,3,7,8],[1,2,3,7,8,9],[1,2,3,7,8,9,10],[1,2,3,7,8,10],[1,2,3,7,9],[1,2,3,7,9,10],[1,2,3,7,10],[1,2,3,8],[1,2,3,8,9],[1,2,3,8,9,10],[1,2,3,8,10],[1,2,3,9],[1,2,3,9,10],[1,2,3,10],[1,2,4],[1,2,4,5],[1,2,4,5,6],[1,2,4,5,6,7],[1,2,4,5,6,7,8],[1,2,4,5,6,7,8,9],[1,2,4,5,6,7,8,9,10],[1,2,4,5,6,7,8,10],[1,2,4,5,6,7,9],[1,2,4,5,6,7,9,10],[1,2,4,5,6,7,10],[1,2,4,5,6,8],[1,2,4,5,6,8,9],[1,2,4,5,6,8,9,10],[1,2,4,5,6,8,10],[1,2,4,5,6,9],[1,2,4,5,6,9,10],[1,2,4,5,6,10],[1,2,4,5,7],[1,2,4,5,7,8],[1,2,4,5,7,8,9],[1,2,4,5,7,8,9,10],[1,2,4,5,7,8,10],[1,2,4,5,7,9],[1,2,4,5,7,9,10],[1,2,4,5,7,10],[1,2,4,5,8],[1,2,4,5,8,9],[1,2,4,5,8,9,10],[1,2,4,5,8,10],[1,2,4,5,9],[1,2,4,5,9,10],[1,2,4,5,10],[1,2,4,6],[1,2,4,6,7],[1,2,4,6,7,8],[1,2,4,6,7,8,9],[1,2,4,6,7,8,9,10],[1,2,4,6,7,8,10],[1,2,4,6,7,9],[1,2,4,6,7,9,10],[1,2,4,6,7,10],[1,2,4,6,8],[1,2,4,6,8,9],[1,2,4,6,8,9,10],[1,2,4,6,8,10],[1,2,4,6,9],[1,2,4,6,9,10],[1,2,4,6,10],[1,2,4,7],[1,2,4,7,8],[1,2,4,7,8,9],[1,2,4,7,8,9,10],[1,2,4,7,8,10],[1,2,4,7,9],[1,2,4,7,9,10],[1,2,4,7,10],[1,2,4,8],[1,2,4,8,9],[1,2,4,8,9,10],[1,2,4,8,10],[1,2,4,9],[1,2,4,9,10],[1,2,4,10],[1,2,5],[1,2,5,6],[1,2,5,6,7],[1,2,5,6,7,8],[1,2,5,6,7,8,9],[1,2,5,6,7,8,9,10],[1,2,5,6,7,8,10],[1,2,5,6,7,9],[1,2,5,6,7,9,10],[1,2,5,6,7,10],[1,2,5,6,8],[1,2,5,6,8,9],[1,2,5,6,8,9,10],[1,2,5,6,8,10],[1,2,5,6,9],[1,2,5,6,9,10],[1,2,5,6,10],[1,2,5,7],[1,2,5,7,8],[1,2,5,7,8,9],[1,2,5,7,8,9,10],[1,2,5,7,8,10],[1,2,5,7,9],[1,2,5,7,9,10],[1,2,5,7,10],[1,2,5,8],[1,2,5,8,9],[1,2,5,8,9,10],[1,2,5,8,10],[1,2,5,9],[1,2,5,9,10],[1,2,5,10],[1,2,6],[1,2,6,7],[1,2,6,7,8],[1,2,6,7,8,9],[1,2,6,7,8,9,10],[1,2,6,7,8,10],[1,2,6,7,9],[1,2,6,7,9,10],[1,2,6,7,10],[1,2,6,8],[1,2,6,8,9],[1,2,6,8,9,10],[1,2,6,8,10],[1,2,6,9],[1,2,6,9,10],[1,2,6,10],[1,2,7],[1,2,7,8],[1,2,7,8,9],[1,2,7,8,9,10],[1,2,7,8,10],[1,2,7,9],[1,2,7,9,10],[1,2,7,10],[1,2,8],[1,2,8,9],[1,2,8,9,10],[1,2,8,10],[1,2,9],[1,2,9,10],[1,2,10],[1,3],[1,3,4],[1,3,4,5],[1,3,4,5,6],[1,3,4,5,6,7],[1,3,4,5,6,7,8],[1,3,4,5,6,7,8,9],[1,3,4,5,6,7,8,9,10],[1,3,4,5,6,7,8,10],[1,3,4,5,6,7,9],[1,3,4,5,6,7,9,10],[1,3,4,5,6,7,10],[1,3,4,5,6,8],[1,3,4,5,6,8,9],[1,3,4,5,6,8,9,10],[1,3,4,5,6,8,10],[1,3,4,5,6,9],[1,3,4,5,6,9,10],[1,3,4,5,6,10],[1,3,4,5,7],[1,3,4,5,7,8],[1,3,4,5,7,8,9],[1,3,4,5,7,8,9,10],[1,3,4,5,7,8,10],[1,3,4,5,7,9],[1,3,4,5,7,9,10],[1,3,4,5,7,10],[1,3,4,5,8],[1,3,4,5,8,9],[1,3,4,5,8,9,10],[1,3,4,5,8,10],[1,3,4,5,9],[1,3,4,5,9,10],[1,3,4,5,10],[1,3,4,6],[1,3,4,6,7],[1,3,4,6,7,8],[1,3,4,6,7,8,9],[1,3,4,6,7,8,9,10],[1,3,4,6,7,8,10],[1,3,4,6,7,9],[1,3,4,6,7,9,10],[1,3,4,6,7,10],[1,3,4,6,8],[1,3,4,6,8,9],[1,3,4,6,8,9,10],[1,3,4,6,8,10],[1,3,4,6,9],[1,3,4,6,9,10],[1,3,4,6,10],[1,3,4,7],[1,3,4,7,8],[1,3,4,7,8,9],[1,3,4,7,8,9,10],[1,3,4,7,8,10],[1,3,4,7,9],[1,3,4,7,9,10],[1,3,4,7,10],[1,3,4,8],[1,3,4,8,9],[1,3,4,8,9,10],[1,3,4,8,10],[1,3,4,9],[1,3,4,9,10],[1,3,4,10],[1,3,5],[1,3,5,6],[1,3,5,6,7],[1,3,5,6,7,8],[1,3,5,6,7,8,9],[1,3,5,6,7,8,9,10],[1,3,5,6,7,8,10],[1,3,5,6,7,9],[1,3,5,6,7,9,10],[1,3,5,6,7,10],[1,3,5,6,8],[1,3,5,6,8,9],[1,3,5,6,8,9,10],[1,3,5,6,8,10],[1,3,5,6,9],[1,3,5,6,9,10],[1,3,5,6,10],[1,3,5,7],[1,3,5,7,8],[1,3,5,7,8,9],[1,3,5,7,8,9,10],[1,3,5,7,8,10],[1,3,5,7,9],[1,3,5,7,9,10],[1,3,5,7,10],[1,3,5,8],[1,3,5,8,9],[1,3,5,8,9,10],[1,3,5,8,10],[1,3,5,9],[1,3,5,9,10],[1,3,5,10],[1,3,6],[1,3,6,7],[1,3,6,7,8],[1,3,6,7,8,9],[1,3,6,7,8,9,10],[1,3,6,7,8,10],[1,3,6,7,9],[1,3,6,7,9,10],[1,3,6,7,10],[1,3,6,8],[1,3,6,8,9],[1,3,6,8,9,10],[1,3,6,8,10],[1,3,6,9],[1,3,6,9,10],[1,3,6,10],[1,3,7],[1,3,7,8],[1,3,7,8,9],[1,3,7,8,9,10],[1,3,7,8,10],[1,3,7,9],[1,3,7,9,10],[1,3,7,10],[1,3,8],[1,3,8,9],[1,3,8,9,10],[1,3,8,10],[1,3,9],[1,3,9,10],[1,3,10],[1,4],[1,4,5],[1,4,5,6],[1,4,5,6,7],[1,4,5,6,7,8],[1,4,5,6,7,8,9],[1,4,5,6,7,8,9,10],[1,4,5,6,7,8,10],[1,4,5,6,7,9],[1,4,5,6,7,9,10],[1,4,5,6,7,10],[1,4,5,6,8],[1,4,5,6,8,9],[1,4,5,6,8,9,10],[1,4,5,6,8,10],[1,4,5,6,9],[1,4,5,6,9,10],[1,4,5,6,10],[1,4,5,7],[1,4,5,7,8],[1,4,5,7,8,9],[1,4,5,7,8,9,10],[1,4,5,7,8,10],[1,4,5,7,9],[1,4,5,7,9,10],[1,4,5,7,10],[1,4,5,8],[1,4,5,8,9],[1,4,5,8,9,10],[1,4,5,8,10],[1,4,5,9],[1,4,5,9,10],[1,4,5,10],[1,4,6],[1,4,6,7],[1,4,6,7,8],[1,4,6,7,8,9],[1,4,6,7,8,9,10],[1,4,6,7,8,10],[1,4,6,7,9],[1,4,6,7,9,10],[1,4,6,7,10],[1,4,6,8],[1,4,6,8,9],[1,4,6,8,9,10],[1,4,6,8,10],[1,4,6,9],[1,4,6,9,10],[1,4,6,10],[1,4,7],[1,4,7,8],[1,4,7,8,9],[1,4,7,8,9,10],[1,4,7,8,10],[1,4,7,9],[1,4,7,9,10],[1,4,7,10],[1,4,8],[1,4,8,9],[1,4,8,9,10],[1,4,8,10],[1,4,9],[1,4,9,10],[1,4,10],[1,5],[1,5,6],[1,5,6,7],[1,5,6,7,8],[1,5,6,7,8,9],[1,5,6,7,8,9,10],[1,5,6,7,8,10],[1,5,6,7,9],[1,5,6,7,9,10],[1,5,6,7,10],[1,5,6,8],[1,5,6,8,9],[1,5,6,8,9,10],[1,5,6,8,10],[1,5,6,9],[1,5,6,9,10],[1,5,6,10],[1,5,7],[1,5,7,8],[1,5,7,8,9],[1,5,7,8,9,10],[1,5,7,8,10],[1,5,7,9],[1,5,7,9,10],[1,5,7,10],[1,5,8],[1,5,8,9],[1,5,8,9,10],[1,5,8,10],[1,5,9],[1,5,9,10],[1,5,10],[1,6],[1,6,7],[1,6,7,8],[1,6,7,8,9],[1,6,7,8,9,10],[1,6,7,8,10],[1,6,7,9],[1,6,7,9,10],[1,6,7,10],[1,6,8],[1,6,8,9],[1,6,8,9,10],[1,6,8,10],[1,6,9],[1,6,9,10],[1,6,10],[1,7],[1,7,8],[1,7,8,9],[1,7,8,9,10],[1,7,8,10],[1,7,9],[1,7,9,10],[1,7,10],[1,8],[1,8,9],[1,8,9,10],[1,8,10],[1,9],[1,9,10],[1,10],[1,1],[1,1,1],[1,1,1,1],[1,1,1,1,1],[1,1,1,1,1,1],[2,3],[2,3,4],[2,3,4,5],[2,3,4,5,6],[2,3,4,5,6,7],[2,3,4,5,6,7,8],[2,3,4,5,6,7,8,9],[2,3,4,5,6,7,8,9,10],[2,3,4,5,6,7,8,10],[2,3,4,5,6,7,9],[2,3,4,5,6,7,9,10],[2,3,4,5,6,7,10],[2,3,4,5,6,8],[2,3,4,5,6,8,9],[2,3,4,5,6,8,9,10],[2,3,4,5,6,8,10],[2,3,4,5,6,9],[2,3,4,5,6,9,10],[2,3,4,5,6,10],[2,3,4,5,7],[2,3,4,5,7,8],[2,3,4,5,7,8,9],[2,3,4,5,7,8,9,10],[2,3,4,5,7,8,10],[2,3,4,5,7,9],[2,3,4,5,7,9,10],[2,3,4,5,7,10],[2,3,4,5,8],[2,3,4,5,8,9],[2,3,4,5,8,9,10],[2,3,4,5,8,10],[2,3,4,5,9],[2,3,4,5,9,10],[2,3,4,5,10],[2,3,4,6],[2,3,4,6,7],[2,3,4,6,7,8],[2,3,4,6,7,8,9],[2,3,4,6,7,8,9,10],[2,3,4,6,7,8,10],[2,3,4,6,7,9],[2,3,4,6,7,9,10],[2,3,4,6,7,10],[2,3,4,6,8],[2,3,4,6,8,9],[2,3,4,6,8,9,10],[2,3,4,6,8,10],[2,3,4,6,9],[2,3,4,6,9,10],[2,3,4,6,10],[2,3,4,7],[2,3,4,7,8],[2,3,4,7,8,9],[2,3,4,7,8,9,10],[2,3,4,7,8,10],[2,3,4,7,9],[2,3,4,7,9,10],[2,3,4,7,10],[2,3,4,8],[2,3,4,8,9],[2,3,4,8,9,10],[2,3,4,8,10],[2,3,4,9],[2,3,4,9,10],[2,3,4,10],[2,3,5],[2,3,5,6],[2,3,5,6,7],[2,3,5,6,7,8],[2,3,5,6,7,8,9],[2,3,5,6,7,8,9,10],[2,3,5,6,7,8,10],[2,3,5,6,7,9],[2,3,5,6,7,9,10],[2,3,5,6,7,10],[2,3,5,6,8],[2,3,5,6,8,9],[2,3,5,6,8,9,10],[2,3,5,6,8,10],[2,3,5,6,9],[2,3,5,6,9,10],[2,3,5,6,10],[2,3,5,7],[2,3,5,7,8],[2,3,5,7,8,9],[2,3,5,7,8,9,10],[2,3,5,7,8,10],[2,3,5,7,9],[2,3,5,7,9,10],[2,3,5,7,10],[2,3,5,8],[2,3,5,8,9],[2,3,5,8,9,10],[2,3,5,8,10],[2,3,5,9],[2,3,5,9,10],[2,3,5,10],[2,3,6],[2,3,6,7],[2,3,6,7,8],[2,3,6,7,8,9],[2,3,6,7,8,9,10],[2,3,6,7,8,10],[2,3,6,7,9],[2,3,6,7,9,10],[2,3,6,7,10],[2,3,6,8],[2,3,6,8,9],[2,3,6,8,9,10],[2,3,6,8,10],[2,3,6,9],[2,3,6,9,10],[2,3,6,10],[2,3,7],[2,3,7,8],[2,3,7,8,9],[2,3,7,8,9,10],[2,3,7,8,10],[2,3,7,9],[2,3,7,9,10],[2,3,7,10],[2,3,8],[2,3,8,9],[2,3,8,9,10],[2,3,8,10],[2,3,9],[2,3,9,10],[2,3,10],[2,4],[2,4,5],[2,4,5,6],[2,4,5,6,7],[2,4,5,6,7,8],[2,4,5,6,7,8,9],[2,4,5,6,7,8,9,10],[2,4,5,6,7,8,10],[2,4,5,6,7,9],[2,4,5,6,7,9,10],[2,4,5,6,7,10],[2,4,5,6,8],[2,4,5,6,8,9],[2,4,5,6,8,9,10],[2,4,5,6,8,10],[2,4,5,6,9],[2,4,5,6,9,10],[2,4,5,6,10],[2,4,5,7],[2,4,5,7,8],[2,4,5,7,8,9],[2,4,5,7,8,9,10],[2,4,5,7,8,10],[2,4,5,7,9],[2,4,5,7,9,10],[2,4,5,7,10],[2,4,5,8],[2,4,5,8,9],[2,4,5,8,9,10],[2,4,5,8,10],[2,4,5,9],[2,4,5,9,10],[2,4,5,10],[2,4,6],[2,4,6,7],[2,4,6,7,8],[2,4,6,7,8,9],[2,4,6,7,8,9,10],[2,4,6,7,8,10],[2,4,6,7,9],[2,4,6,7,9,10],[2,4,6,7,10],[2,4,6,8],[2,4,6,8,9],[2,4,6,8,9,10],[2,4,6,8,10],[2,4,6,9],[2,4,6,9,10],[2,4,6,10],[2,4,7],[2,4,7,8],[2,4,7,8,9],[2,4,7,8,9,10],[2,4,7,8,10],[2,4,7,9],[2,4,7,9,10],[2,4,7,10],[2,4,8],[2,4,8,9],[2,4,8,9,10],[2,4,8,10],[2,4,9],[2,4,9,10],[2,4,10],[2,5],[2,5,6],[2,5,6,7],[2,5,6,7,8],[2,5,6,7,8,9],[2,5,6,7,8,9,10],[2,5,6,7,8,10],[2,5,6,7,9],[2,5,6,7,9,10],[2,5,6,7,10],[2,5,6,8],[2,5,6,8,9],[2,5,6,8,9,10],[2,5,6,8,10],[2,5,6,9],[2,5,6,9,10],[2,5,6,10],[2,5,7],[2,5,7,8],[2,5,7,8,9],[2,5,7,8,9,10],[2,5,7,8,10],[2,5,7,9],[2,5,7,9,10],[2,5,7,10],[2,5,8],[2,5,8,9],[2,5,8,9,10],[2,5,8,10],[2,5,9],[2,5,9,10],[2,5,10],[2,6],[2,6,7],[2,6,7,8],[2,6,7,8,9],[2,6,7,8,9,10],[2,6,7,8,10],[2,6,7,9],[2,6,7,9,10],[2,6,7,10],[2,6,8],[2,6,8,9],[2,6,8,9,10],[2,6,8,10],[2,6,9],[2,6,9,10],[2,6,10],[2,7],[2,7,8],[2,7,8,9],[2,7,8,9,10],[2,7,8,10],[2,7,9],[2,7,9,10],[2,7,10],[2,8],[2,8,9],[2,8,9,10],[2,8,10],[2,9],[2,9,10],[2,10],[3,4],[3,4,5],[3,4,5,6],[3,4,5,6,7],[3,4,5,6,7,8],[3,4,5,6,7,8,9],[3,4,5,6,7,8,9,10],[3,4,5,6,7,8,10],[3,4,5,6,7,9],[3,4,5,6,7,9,10],[3,4,5,6,7,10],[3,4,5,6,8],[3,4,5,6,8,9],[3,4,5,6,8,9,10],[3,4,5,6,8,10],[3,4,5,6,9],[3,4,5,6,9,10],[3,4,5,6,10],[3,4,5,7],[3,4,5,7,8],[3,4,5,7,8,9],[3,4,5,7,8,9,10],[3,4,5,7,8,10],[3,4,5,7,9],[3,4,5,7,9,10],[3,4,5,7,10],[3,4,5,8],[3,4,5,8,9],[3,4,5,8,9,10],[3,4,5,8,10],[3,4,5,9],[3,4,5,9,10],[3,4,5,10],[3,4,6],[3,4,6,7],[3,4,6,7,8],[3,4,6,7,8,9],[3,4,6,7,8,9,10],[3,4,6,7,8,10],[3,4,6,7,9],[3,4,6,7,9,10],[3,4,6,7,10],[3,4,6,8],[3,4,6,8,9],[3,4,6,8,9,10],[3,4,6,8,10],[3,4,6,9],[3,4,6,9,10],[3,4,6,10],[3,4,7],[3,4,7,8],[3,4,7,8,9],[3,4,7,8,9,10],[3,4,7,8,10],[3,4,7,9],[3,4,7,9,10],[3,4,7,10],[3,4,8],[3,4,8,9],[3,4,8,9,10],[3,4,8,10],[3,4,9],[3,4,9,10],[3,4,10],[3,5],[3,5,6],[3,5,6,7],[3,5,6,7,8],[3,5,6,7,8,9],[3,5,6,7,8,9,10],[3,5,6,7,8,10],[3,5,6,7,9],[3,5,6,7,9,10],[3,5,6,7,10],[3,5,6,8],[3,5,6,8,9],[3,5,6,8,9,10],[3,5,6,8,10],[3,5,6,9],[3,5,6,9,10],[3,5,6,10],[3,5,7],[3,5,7,8],[3,5,7,8,9],[3,5,7,8,9,10],[3,5,7,8,10],[3,5,7,9],[3,5,7,9,10],[3,5,7,10],[3,5,8],[3,5,8,9],[3,5,8,9,10],[3,5,8,10],[3,5,9],[3,5,9,10],[3,5,10],[3,6],[3,6,7],[3,6,7,8],[3,6,7,8,9],[3,6,7,8,9,10],[3,6,7,8,10],[3,6,7,9],[3,6,7,9,10],[3,6,7,10],[3,6,8],[3,6,8,9],[3,6,8,9,10],[3,6,8,10],[3,6,9],[3,6,9,10],[3,6,10],[3,7],[3,7,8],[3,7,8,9],[3,7,8,9,10],[3,7,8,10],[3,7,9],[3,7,9,10],[3,7,10],[3,8],[3,8,9],[3,8,9,10],[3,8,10],[3,9],[3,9,10],[3,10],[4,5],[4,5,6],[4,5,6,7],[4,5,6,7,8],[4,5,6,7,8,9],[4,5,6,7,8,9,10],[4,5,6,7,8,10],[4,5,6,7,9],[4,5,6,7,9,10],[4,5,6,7,10],[4,5,6,8],[4,5,6,8,9],[4,5,6,8,9,10],[4,5,6,8,10],[4,5,6,9],[4,5,6,9,10],[4,5,6,10],[4,5,7],[4,5,7,8],[4,5,7,8,9],[4,5,7,8,9,10],[4,5,7,8,10],[4,5,7,9],[4,5,7,9,10],[4,5,7,10],[4,5,8],[4,5,8,9],[4,5,8,9,10],[4,5,8,10],[4,5,9],[4,5,9,10],[4,5,10],[4,6],[4,6,7],[4,6,7,8],[4,6,7,8,9],[4,6,7,8,9,10],[4,6,7,8,10],[4,6,7,9],[4,6,7,9,10],[4,6,7,10],[4,6,8],[4,6,8,9],[4,6,8,9,10],[4,6,8,10],[4,6,9],[4,6,9,10],[4,6,10],[4,7],[4,7,8],[4,7,8,9],[4,7,8,9,10],[4,7,8,10],[4,7,9],[4,7,9,10],[4,7,10],[4,8],[4,8,9],[4,8,9,10],[4,8,10],[4,9],[4,9,10],[4,10],[5,6],[5,6,7],[5,6,7,8],[5,6,7,8,9],[5,6,7,8,9,10],[5,6,7,8,10],[5,6,7,9],[5,6,7,9,10],[5,6,7,10],[5,6,8],[5,6,8,9],[5,6,8,9,10],[5,6,8,10],[5,6,9],[5,6,9,10],[5,6,10],[5,7],[5,7,8],[5,7,8,9],[5,7,8,9,10],[5,7,8,10],[5,7,9],[5,7,9,10],[5,7,10],[5,8],[5,8,9],[5,8,9,10],[5,8,10],[5,9],[5,9,10],[5,10],[6,7],[6,7,8],[6,7,8,9],[6,7,8,9,10],[6,7,8,10],[6,7,9],[6,7,9,10],[6,7,10],[6,8],[6,8,9],[6,8,9,10],[6,8,10],[6,9],[6,9,10],[6,10],[7,8],[7,8,9],[7,8,9,10],[7,8,10],[7,9],[7,9,10],[7,10],[8,9],[8,9,10],[8,10],[9,10]]
	stdout:

省流版：


> 2024/04/03 15:11:09	
Wrong Answer:
	input:[1,2,3,4,5,6,7,8,9,10,1,1,1,1,1]
	Output:[...,[1,9],[1,9,10],[1,10],[1,1],[1,1,1],[1,1,1,1],[1,1,1,1,1],[1,1,1,1,1,1],[2,3],[2,3,4],...,[8,9],[8,9,10],[8,10],[9,10],[1,1],[1,1,1],[1,1,1,1],[1,1,1,1,1],[1,1],[1,1,1],[1,1,1,1],[1,1],[1,1,1],[1,1]]
	Expected:[...,[1,9],[1,9,10],[1,10],[1,1],[1,1,1],[1,1,1,1],[1,1,1,1,1],[1,1,1,1,1,1],[2,3],[2,3,4],...,[8,9],[8,9,10],[8,10],[9,10]]
	stdout:

2 LeetCode46 全排列

题目

给定一个不含重复数字的数组 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]]

提示：

1 <= nums.length <= 6
-10 <= nums[i] <= 10
nums 中的所有整数互不相同

回溯秒了。注意排列问题是不需要记录start_index的，排列问题始终需要对所有元素进行循环。但是排列问题需要树枝查重，以避免选到相同的元素。

python
from typing import List

class Solution:
    def __init__(self):
        self.path = []
        self.result = []
        self.nums = []

    def permute(self, nums: List[int]) -> List[List[int]]:
        self.nums = nums
        self.back_tracking()
        return self.result

    def back_tracking(self):
        if len(self.path) == len(self.nums):
            self.result.append(self.path.copy())
        for i in self.nums:
            if i not in self.path:  # 这是一种偷懒写法 它偷懒的点是题目给定的数组不包含重复元素
                self.path.append(i)
                self.back_tracking()
                self.path.pop()

3 LeetCode47 全排列Ⅱ

题目

给定一个可包含重复数字的序列 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]]

提示：

1 <= nums.length <= 8
-10 <= nums[i] <= 10

回溯秒了。这次需要树枝查重+递归查重两个相结合。递归查重是为了避免相同排列的产生。

python
from typing import List

class Solution:
    def __init__(self):
        self.path = []
        self.result = []
        self.nums = []
        self.index_used = [0] * 8  # 它负责树枝查重

    def permuteUnique(self, nums: List[int]) -> List[List[int]]:
        self.nums = nums
        self.back_tracking()
        return self.result

    def back_tracking(self):
        if len(self.path) == len(self.nums):
            self.result.append(self.path.copy())
        number_used = [0] * 21  # 它负责递归查重
        for i in range(len(self.nums)):
            if self.index_used[i] == 0:
                if number_used[self.nums[i]] == 0:
                    self.path.append(self.nums[i])
                    number_used[self.nums[i]] = 1
                    self.index_used[i] = 1
                    self.back_tracking()
                    self.path.pop()
                    self.index_used[i] = 0  # 树枝查重是需要递归结束时置回去的

目录

1 LeetCode491 递增子序列

2 LeetCode46 全排列

3 LeetCode47 全排列Ⅱ