leetcode 78、子集

本文主要是介绍leetcode 78、子集，对大家解决编程问题具有一定的参考价值，需要的程序猿们随着小编来一起学习吧！

1、题目

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

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

示例 1：

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

2、解答

• 暴力法：说是暴力法，其实我个人觉得这种方法是最好的。遍历nums的每个元素，将这个元素插入到之前已经获得的子集中的每一个元素里面去就会获得新的元素，那么结果集就是res[i] =res[i-1] + [res[i-1],i]。

这道题也可以深度优先和广度优先来解答。就是得画出对应的树结构来就一目了然了。(使用的有道笔记非会员不能直接插入图片，就简单画了一个图)

graph TB
0-->1
0-->2
0-->3
1-->2'
1-->3'
2'-->3''
2-->3'''

上图中0其实代表的就是空列表[].

-深度优先遍历：就是遍历获得的数组长度小于等于nums长度时就是子集元素。
-广度优先遍历：就是子集元素长度从0,1,2一直到len(nums).

import copy

class Solution(object):
    def subsets(self, nums):
        """
        暴力法：就是按照遍历顺序每次添加一个元素进行扩展。
        :type nums: List[int]
        :rtype: List[List[int]]
        """
        res = []
        res.append([])
        for i in nums:
            tmp = copy.deepcopy(res)
            for num in tmp:
                num.append(i)
                res.append(num)
        return res

    def subsets2(self, nums):
        """
        深度优先遍历：优先深度遍历
        :type nums: List[int]
        :rtype: List[List[int]]
        """
        res = []
        self.dfs(nums, 0, res, [])
        return res

    def dfs(self, nums, begin, res, tmp_list):
        if len(tmp_list)<=len(nums):
            res.append(copy.deepcopy(tmp_list))

        for index in range(begin,len(nums)):
            tmp_list.append(nums[index])
            self.dfs(nums, index+1, res, tmp_list)
            tmp_list.pop()

    def subsets3(self, nums):
        """
        回溯法：这个其实也可以理解为宽度优先遍历，就是以子集长度为优先遍历条件。
        :type nums: List[int]
        :rtype: List[List[int]]
        """
        res = []
        res.append([])
        for i in range(1, len(nums)+1):
            self.back_trace(nums, res, 0, [], i)
        return res

    def back_trace(self, nums, res, begin, tmp_list, target):
        if len(tmp_list)==target:
            res.append(copy.deepcopy(tmp_list))
            return

        for index in range(begin, len(nums)):
            tmp_list.append(nums[index])
            self.back_trace(nums, res, index+1, tmp_list, target)
            tmp_list.pop()

这篇关于leetcode 78、子集的文章就介绍到这儿，希望我们推荐的文章对大家有所帮助，也希望大家多多支持为之网！