网站建设项目规划书社团宣传,邢台专业网站建设公司,北京做的好的seo公司,西安学校网站建设哪家好文章目录 题目链接解题思路解题代码 题目链接
78. 子集
给你一个整数数组 nums #xff0c;数组中的元素 互不相同 。返回该数组所有可能的子集#xff08;幂集#xff09;。
解集 不能 包含重复的子集。你可以按 任意顺序 返回解集。
示例 1#xff1a; 输入#xff… 文章目录 题目链接解题思路解题代码 题目链接
78. 子集
给你一个整数数组 nums 数组中的元素 互不相同 。返回该数组所有可能的子集幂集。
解集 不能 包含重复的子集。你可以按 任意顺序 返回解集。
示例 1 输入nums [1,2,3] 输出[[],[1],[2],[1,2],[3],[1,3],[2,3],[1,2,3]]
示例 2 输入nums [0] 输出[[],[0]]
解题思路
回溯算法 下面我们根据回溯算法三步走写出对应的回溯算法。
1.明确所有选择根据数组中每个位置上的元素选与不选两种选择。2.明确终止条件当遍历到决策树的叶子节点时就终止了。即当前路径搜索到末尾时递归终止。3.将决策树和终止条件翻译成代码 定义回溯函数 backtracking(nums, index): 函数的传入参数是 nums可选数组列表和 index代表当前正在考虑元素是 nums[i] 全局变量是 res存放所有符合条件结果的集合数组和 path存放当前符合条件的结果。backtracking(nums, index): 函数代表的含义是在选择 nums[index] 的情况下递归选择剩下的元素。 书写回溯函数主体给出选择元素、递归搜索、撤销选择部分。 从当前正在考虑元素到数组结束为止枚举出所有可选的元素。对于每一个可选元素 约束条件之前选过的元素不再重复选用。每次从 index 位置开始遍历而不是从 0 位置开始遍历就是为了避免重复。集合跟全排列不一样子集中 {1, 2} 和 {2, 1} 是等价的。为了避免重复我们之前考虑过的元素就不再重复考虑了。 选择元素将其添加到当前子集数组 path 中。 递归搜索在选择该元素的情况下继续递归考虑下一个位置上的元素。 撤销选择将该元素从当前子集数组 path 中移除。 for i in range(index, len(nums)): # 枚举可选元素列表path.append(nums[i]) # 选择元素backtracking(nums, i 1) # 递归搜索path.pop() # 撤销选择明确递归终止条件给出递归终止条件以及递归终止时的处理方法。 当遍历到决策树的叶子节点时就终止了。也就是当正在考虑的元素位置到达数组末尾即 start len(nums)时递归停止。从决策树中也可以看出子集需要存储的答案集合应该包含决策树上所有的节点应该需要保存递归搜索的所有状态。所以无论是否达到终止条件我们都应该将当前符合条件的结果放入到集合中。
解题代码
class Solution:def subsets(self, nums: List[int]) - List[List[int]]:res [] # 存放所有符合条件结果的集合path [] # 存放当前符合条件的结果def backtracking(nums, index): # 正在考虑可选元素列表中第 index 个元素res.append(path[:]) # 将当前符合条件的结果放入集合中if index len(nums): # 遇到终止条件本题returnfor i in range(index, len(nums)): # 枚举可选元素列表path.append(nums[i]) # 选择元素backtracking(nums, i 1) # 递归搜索path.pop() # 撤销选择backtracking(nums, 0)return res参考资料datawhalechina
