[数据结构与算法]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()