【python】Leetcode（primer-set）

更多 leetcode 题解可参考：【Programming】

---

78. 子集（集合的所有子集）

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

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

思路：可以迭代，可以回溯，
算 1 的子集的时候，新增 1 结合 空集；
算 2 的子集的时候，2 结合 1 的所有子集；
算 3 的子集的时候，3 结合 2 的所有子集
…

class Solution(object):def subsets(self, nums):""":type nums: List[int]:rtype: List[List[int]]"""result = [[]]for i in nums:result.extend([j + [i] for j in result])return result

相似题目 1863. 找出所有子集的异或总和再求和

---

90. 子集 II（集合的所有子集）

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

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

思路：和 78 唯一不同的是 nums 可能包含一样的元素，这个时候就会存在 [1,2] 和 [2,1] 或者更难一点的 [1,2,2] 和 [2,1,2] 的情况，78 的解法这两个都会保留（78中元素不一样），但是这题只能保留其中一种！
简单的 set 好像排除不了，我用的是 sorted

class Solution(object):def subsetsWithDup(self, nums):""":type nums: List[int]:rtype: List[List[int]]"""result = [[]]for i in nums:result.extend([j + [i] for j in result])set1 = set(tuple(sorted(item)) for item in result) # tuple 才能 hash——set，sorted 配合set来去重list1 = list(list(item) for item in set1)# 转化成输出的格式return list1