[Leetcode][python]Subsets/Subsets II/子集/子集 II

蛮三刀酱

发布于 2019-03-26 16:22:56

1.5K0

文章被收录于专栏：蛮三刀的后端开发专栏蛮三刀的后端开发专栏

Subsets

题目大意

给定一个由不同数字组成的集合，罗列出该集合的所有子集。

解题思路

见下方代码

代码

纯思路

参考： https://shenjie1993.gitbooks.io/leetcode-python/078%20Subsets.html 举个例子，集合[1]有[[],[1]]两个子集，当向其中添加一个元素时，[1,2]有[[],[1],[2],[1,2]]四个子集，可以看出来，在新添加一个元素的时候，是在原来子集的基础上，添加原子集中所有元素加上新元素的总集合。为了每个子集中的元素都是不降序的，要先把所有元素都排序。

class Solution(object):
    def subsets(self, nums):
        """
        :type nums: List[int]
        :rtype: List[List[int]]
        """
        result = [[]]
        for num in sorted(nums):
            result += [item + [num] for item in result]
        return result

沿用排列题DFS

class Solution(object):
    def subsets(self, nums):
        """
        :type nums: List[int]
        :rtype: List[List[int]]
        """
        self.result = []
        nums.sort()
        for i in range(0, len(nums)+1):
            self.k = i
            self.combineHelper(0, [], nums)
        return self.result

    def combineHelper(self, length, temp, list_num):
        if length == self.k:
            self.result.append(temp[:])  # 需要用切片浅复制出一个新数组
            return
        for i, num in enumerate(list_num):
            temp.append(num)
            self.combineHelper(length+1, temp, list_num[i+1:])
            temp.pop()

Subsets II

题目大意

给定一个由不同数字组成的集合，罗列出该集合的所有子集。 有重复

解题思路

和上一题相同，问题在于如果有重复则会生成多余的子集。参考：https://shenjie1993.gitbooks.io/leetcode-python/078%20Subsets.html 现在举个例子，集合[1]有[[],[1]]两个子集，当向其中添加一个元素时，[1,2]有[[],[1],[2],[1,2]]四个子集，可以看出来，在新添加一个元素的时候，是在原来子集的基础上，添加原子集中所有元素加上新元素的总集合。为了每个子集中的元素都是不降序的，要先把所有元素都排序。

代码

沿用排列题DFS

class Solution(object):
    def subsetsWithDup(self, nums):
        """
        :type nums: List[int]
        :rtype: List[List[int]]
        """
        result = [[]]
        nums.sort()  # sort()直接修改原数组，sorted()返回排序后的数组，不修改原数组
        temp_size = 0
        for i in range(len(nums)):
            start = temp_size if i >= 1 and nums[i] == nums[i - 1] else 0
            temp_size = len(result)  # 每次取到result最后一位，也就是从start一直到最后一位
            for j in range(start, temp_size):
                result.append(result[j] + [nums[i]])
            print result
        return result

总结

纯思路做法显然效率更高，此题标签还有位运算做法，有空。

本文参与腾讯云自媒体同步曝光计划，分享自作者个人站点/博客。

原始发表：2017年10月21日，如有侵权请联系 cloudcommunity@tencent.com 删除

python

html

编程算法