Given a set of distinct integers, nums, return all possible subsets (the power set).
Note: The solution set must not contain duplicate subsets.
Example:
Input: nums = [1,2,3] Output: [ [3], [1], [2], [1,2,3], [1,3], [2,3], [1,2], [] ]
class Solution(object): def subsets(self,nums): """ :param nums:List[int] :return: List[List[int]] """ res=[] self.dfs(nums,0,res,[]) return res def dfs(self,nums,start,res,path): res.append(path) for i in range(start,len(nums)): self.dfs(nums,i+1,res,path+[nums[i]])
Given a collection of integers that might contain duplicates, nums, return all possible subsets (the power set).
Note: The solution set must not contain duplicate subsets.
Example:
Input: [1,2,2] Output: [ [2], [1], [1,2,2], [2,2], [1,2], [] ]
这两道题思路十分相像，后者难点在于有重复，如果是利用数据结构去重
比如map之类 的并不好，因为实际相当已经消耗了计算的时间，所以应该在shen
生成的时候就进行控制；
特别注意sort的用法
class Solution(object): def subsetsWithDup(self,nums): """ :param nums:List[int] :return: List[List[int]] """ res=[] cas=sorted(nums) # ans=sorted(nums)和nums.sort()用法 前者需要赋值，后者直接改变自身 print(nums) print(cas) nums.sort() print(nums) self.dfs(nums,0,res,[]) return res def dfs(self,nums,start,res,path): res.append(path) for i in range(start,len(nums)): if (i>start and nums[i]==nums[i-1]):continue self.dfs(nums,i+1,res,path+[nums[i]]) solu=Solution() nums=[4,4,4,1,4] print(solu.subsetsWithDup(nums))
LeetCode开心刷题四十三天——回溯专题78. Subsets 90. Subsets II
原文：https://www.cnblogs.com/Marigolci/p/11541095.html