【时间】2019.05.25
【题目】【力扣】78.子集 （python解法）
题目链接：https://leetcode-cn.com/problems/subsets/
题目描述：
给定一组不含重复元素的整数数组 nums，返回该数组所有可能的子集（幂集）。
说明：解集不能包含重复的子集。
示例:
输入: nums = [1,2,3] 输出: [ [3], [1], [2], [1,2,3], [1,3], [2,3], [1,2], [] ]题目解法：
#方法1：递归方法，[1,2,3] --> （[1] + [2,3]子集)+[2,3]子集 class Solution: def subsets(self, nums) : res = [] if not nums: return [[]] else: sub = self.subsets(nums[1:]) res = res + sub for s in sub: res.append(nums[:1]+s) return res #方法2 位运算方法：对每一位为1的表示这一位的数字存在，例如对于输入[1,2,3] 编码i=001，表示只含有3，编码i=101.表示含有1,3 class Solution: def subsets(self, nums): t=len(nums) res=[] for i in range(2**t): tmp=[] for j in range(t): if i&(1<<j): tmp.append(nums[t-1-j]) res.append(tmp) return res #方法三 排列组合 class Solution: def subsets(self, nums): from itertools import combinations print([list(s) for s in list(combinations(nums, 2))]) return sum([list(combinations(nums, i)) for i in range(len(nums) + 1)], []) #方法四：遇到一个数添加一下 class Solution: def subsets(self, nums): res = [] res.append([]) for x in nums: new = [s+ [x] for s in res] res = res + new return res #方法五：回溯方法 https://leetcode-cn.com/problems/subsets/solution/hui-su-jie-fa-by-jawhiow/ class Solution(object): def __init__(self): self.result_all = None def subsets(self, nums): """ :type nums: List[int] :rtype: List[List[int]] """ self.result_all = [] self.dfs(nums, 0, 0, []) return self.result_all def dfs(self, nums, n, start, result): self.result_all.append(result[:]) if len(nums) == n: return for i in range(start, len(nums)): result.append(nums[i]) self.dfs(nums, n + 1, i + 1, result) result.pop() return s=Solution() nums = [1,2,3] out = s.subsets(nums) print(out)
