【leetcode-Python】-回溯-78. Subsets

概述题目链接https://leetcode.com/problems/subsets/题目描述给定整数数组nums，数组内元素各不相同。返回该数组所有可能的子集。子集不可重复，可按照任意顺序返回解集。示例输入：[1,2,3]输出：[[],[1],[1,2],[1,2,3],[1,3],[2],[2,3],[3]]解题思路子集问题也是回溯算法解决的 题目链接

https://leetcode.com/problems/subsets/

题目描述

给定整数数组nums，数组内元素各不相同。返回该数组所有可能的子集。子集不可重复，可按照任意顺序返回解集。

示例

输入：[1,2,3]

输出：[[],[1],[1,2],[1,2,3],[1,3],[2],[2,3],[3]]

解题思路

子集问题也是回溯算法解决的经典问题。和全排列问题不同，子集问题中集合内部元素是无序的，已经取过的元素不会再取。求[1,2,3]的子集时， 解空间树是这样的：

可以看出子集由各个节点(包括根节点)的路径组成,并且每个节点的选择列表都是在路径元素后面的值。比如对于路径为[1]的节点，其选择列表就是在1后面的元素[2,3]。因此在回溯算法中，需要用一个startIndex变量来标识选择列表开始的位置, nums[startIndex:)为当前路径中还没取用的元素集合即选择列表。

Python实现

class Solution:    def subsets(self, nums: List[int]) -> List[List[int]]:        result = []        tmp_set = []        def backtrack(tmp_set,start_index):            result.append(tmp_set)#将当前节点的路径加入result            #不用手写递归结束条件，当start_index == len(result)时，for循环结束，就自动回溯到上一个节点。            for i in range(start_index,len(nums)):                backtrack(tmp_set+[nums[i]],i+1)        backtrack(tmp_set,0)        return result

 

总结

以上是内存溢出为你收集整理的【leetcode-Python】-回溯-78. Subsets全部内容，希望文章能够帮你解决【leetcode-Python】-回溯-78. Subsets所遇到的程序开发问题。

如果觉得内存溢出网站内容还不错，欢迎将内存溢出网站推荐给程序员好友。