leetcode78,90,491

leetcode78,90,491

文章目录

78. 子集

分析代码（1到k的组合问题）

通过截图 代码（收集所有节点）

通过截图 90. 子集 II

分析代码

通过截图 491. 递增子序列

分析代码

通过截图

78. 子集

给你一个整数数组 nums ，数组中的元素 互不相同 。返回该数组所有可能的子集（幂集）。

解集 不能 包含重复的子集。你可以按 任意顺序 返回解集。

 

示例 1：

输入：nums = [1,2,3]
输出：[[],[1],[2],[1,2],[3],[1,3],[2,3],[1,2,3]]
示例 2：

输入：nums = [0]
输出：[[],[0]]
 

提示：

1 <= nums.length <= 10
-10 <= nums[i] <= 10
nums 中的所有元素 互不相同

分析

1.我之前第一次做的时候把他当成k会变化的组合问题，即每次选k个（k从1到len(nums)）,最后和空集一起添加到结果集合。但他的时间复杂度很高，
因为有太多重复的回溯，比如k=5,那么k添加到5个的时候，之前添加1-4个这个过程会重复，很多步骤走了非常多次！实际上，子集问题和组合问题非常的像。子集问题是取过程中的每一个节点，即树上所有节点。而组合问题则是取叶子节点。所以我们只需要把收集结果代码没有终止条件即可。 代码（1到k的组合问题）

class Solution:
    def subsets(self, nums: List[int]) -> List[List[int]]:
        res = []
        path = []

        def backtrack(start,k):
            if len(path) == k:
                res.append(path[:])
                return

            for i in range(start,len(nums)):
                path.append(nums[i])
                backtrack(i+1,k)
                path.pop()

        for k in range(1,len(nums)+1):  
            backtrack(0,k)
        res.append([])
        return res

通过截图

代码（收集所有节点）

class Solution:
    def subsets(self, nums: List[int]) -> List[List[int]]:
        res = []
        path = []

        def backtrack(start):
            res.append(path[:]) # 没有终止条件
            if len(path) >= len(nums):
                return

            for i in range(start,len(nums)):
                path.append(nums[i])
                backtrack(i+1)
                path.pop()
        backtrack(0)
        return res

通过截图

90. 子集 II

给你一个整数数组 nums ，其中可能包含重复元素，请你返回该数组所有可能的子集（幂集）。

解集 不能 包含重复的子集。返回的解集中，子集可以按 任意顺序 排列。

 

示例 1：

输入：nums = [1,2,2]
输出：[[],[1],[1,2],[1,2,2],[2],[2,2]]
示例 2：

输入：nums = [0]
输出：[[],[0]]
 

提示：

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

分析

由于会有重复元素，必须去重。首先，同一树层是不可以取重复的数的。因为同层取相同的数，后面势必会重复。所以，这题和上题只有一个区别，就是去重。由于只是求子集，所以我们可以先对该数组进行排序。（简单找到重复元素）i>start:保证至少有两个数，防止后续 *** 作越界。nums[i] == nums[i-1]找到重复元素后，continue即可
代码

class Solution:
    def subsetsWithDup(self, nums: List[int]) -> List[List[int]]:
        res = []
        path = []
        nums.sort()

        def backtrack(start):
            res.append(path[:])
            if len(path) >= len(nums):
                return

            for i in range(start,len(nums)):
                if i > start and nums[i] == nums[i-1]:
                    continue
                path.append(nums[i])
                backtrack(i+1)
                path.pop()

        backtrack(0)
        return res

通过截图

491. 递增子序列

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

分析

这题看似很简单，实际没有想的那么好做。一开始，我直接排序，像前面那题一样，但题目说的是子序列（原来顺序不可变），就意味着我们之前用前后位去重的方法失效。我们先确定终止条件，由于题目要求递增子序列至少需要两个元素，所以当path内长度大于等于2时，就把它加入到结果集中，不要return（因为是收集树的所有节点）。设定一个used数组，结果集在加入后，used也加入，如果path不为空且遍历到的元素比path最后一个元素小，或者used数组里已经出现直接continue。注意used只记录本层
代码

class Solution:
    def findSubsequences(self, nums: List[int]) -> List[List[int]]:
        res = []
        path = []
        def backtrack(start):            
            if len(path) >= 2: 
                res.append(path[:])
            used = [] 
            for i in range(start,len(nums)):
                if (path and nums[i] 
通过截图 
 
如有错误，敬请指正，欢迎交流，谢谢♪(･ω･)ﾉ
					
										


					

						
欢迎分享，转载请注明来源：内存溢出
原文地址: http://outofmemory.cn/zaji/5722028.html