Skip to main content

78. 子集 [medium]

78. 子集 [medium]​

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

给定一组不含重复元素的整数数组 nums，返回该数组所有可能的子集（幂集）。

说明：解集不能包含重复的子集。

示例:

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

通过次数101,923 | 提交次数131,546

Second Try​

2020-07-03

这是一个很奇葩的写法，乍看到会有点迷糊，仔细分析才知道在干什么。 参考题解写出来的，现在看起来就是理所当然了。

class Solution(object):
    def subsets(self, nums):
        """
        :type nums: List[int]
        :rtype: List[List[int]]
        """

        rv = [[]]
        for n in nums:
            rv += [r + [n] for r in rv]
            # print(rv)
        return rv
  • 执行用时：20 ms, 在所有 Python 提交中击败了70.33%的用户
  • 内存消耗：12.8 MB, 在所有 Python 提交中击败了8.33%的用户

First Try​

2020-07-03

本来觉得没什么思路的，结果发现每个元素的后一位比前一位大即可避免重复，因此可以放心写个回溯法。

回溯递归法可以解决需要无确定循环调用的问题，真是万能解题法。

class Solution(object):
    def subsets(self, nums):
        """
        :type nums: List[int]
        :rtype: List[List[int]]
        """

        rv = []

        # 不允许包含重复元素，那么按照正序来
        def recurs(nums, seq):
            rv.append(seq)
            if len(seq) == len(nums):
                return 
            for n in nums:
                if len(seq) == 0 or n > seq[-1]:
                    recurs(nums, seq + [n])

        recurs(nums, [])
        return rv
  • 执行用时：16 ms, 在所有 Python 提交中击败了89.47%的用户
  • 内存消耗：12.8 MB, 在所有 Python 提交中击败了8.33%的用户