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

布满荆棘的人生 2022-06-07 12:19 194阅读 0赞

# Subsets #

## 题目大意 ##

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

## 解题思路 ##

见下方代码

## 代码 ##

### 纯思路 ###

参考：  
[https://shenjie1993.gitbooks.io/leetcode-python/078%20Subsets.html][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][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

# 总结 #

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

[https_shenjie1993.gitbooks.io_leetcode-python_078_20Subsets.html]: https://shenjie1993.gitbooks.io/leetcode-python/078%20Subsets.html