人才引进从事网站建设,申请注册一个商标多少钱,公路水运建设质量与安全监督系统网站,建设官网电话号码子集 题目题解1. 迭代2. 双重循环3. 递归4. 回溯 题目
78. 子集
给你一个整数数组 nums #xff0c;数组中的元素 互不相同 。返回该数组所有可能的子集#xff08;幂集#xff09;。
解集 不能 包含重复的子集。你可以按 任意顺序 返回解集。
示例 1#xff1a;
输入… 子集 题目题解1. 迭代2. 双重循环3. 递归4. 回溯 题目
78. 子集
给你一个整数数组 nums 数组中的元素 互不相同 。返回该数组所有可能的子集幂集。
解集 不能 包含重复的子集。你可以按 任意顺序 返回解集。
示例 1
输入nums [1,2,3] 输出[[],[1],[2],[1,2],[3],[1,3],[2,3],[1,2,3]]
示例 2
输入nums [0] 输出[[],[0]]
题解
1. 迭代
思路将子集不断添加到result
class Solution(object):def subsets(self, nums)::type nums: List[int]:rtype: List[List[int]]# 迭代result [[]]for num in nums:result result [[num] res for res in result]return result
2. 双重循环
思路与1类似更好理解
class Solution(object):def subsets(self, nums)::type nums: List[int]:rtype: List[List[int]]# 迭代res [[]]for i in range(len(nums)):for j in range(len(res)):res.append(res[j][nums[i]])return res
3. 递归
class Solution(object):def subsets(self, nums)::type nums: List[int]:rtype: List[List[int]]# 递归ans []path []n len(nums)def dfs(i):if i n:ans.append(path[:])return dfs(i 1)path.append(nums[i])dfs(i 1)path.pop()dfs(0)return ans
4. 回溯
class Solution(object):def subsets(self, nums)::type nums: List[int]:rtype: List[List[int]]# 回溯算法path []ans []n len(nums)def dfs(nums, i):ans.append(path[:])if i n:return for j in range(i, n):path.append(nums[j])dfs(nums, j 1)path.pop()dfs(nums, 0)return ans
