leetcode-子集（python）

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

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

示例:

输入: nums = [1,2,3]
输出:
[
[3],
[1],
[2],
[1,2,3],
[1,3],
[2,3],
[1,2],
[]
]
位运算法：

class Solution:
    def subsets(self, nums):
        allset=2**len(nums)
        result=[]
        for i in range(allset):
            item=[]
            for j in range(len(nums)):
                if i&(2**j):
                    item.append(nums[j])
            result.append(item)
        return result

回溯法：

class Solution:
    def subsets(self, nums):
        item = []
        result = []
        result.append(item)

        def generate(i, nums, item, result):
            if i >= len(nums):
                return
            item.append(nums[i])
            result.append(list(item))
            generate(i + 1, nums, item, result)
            item.pop()
            generate(i + 1, nums, item, result)

        generate(0, nums, item, result)
        return result

有重复元素的情况：先排序，在判断是否已经存在

class Solution:
    def subsetsWithDup(self, nums):
        item = []
        result = [[]]
        nums.sort() #排序
        def generate(i, nums, item, result):
            if i >= len(nums):
                return
            item.append(nums[i])
            if item not in result: #判断
                result.append(list(item))
            generate(i + 1, nums, item, result)
            item.pop()
            generate(i + 1, nums, item, result)

        generate(0, nums, item, result)
        return result

大神版本

class Solution:
    def subsetsWithDup(self, nums: List[int]) -> List[List[int]]:
        nums.sort()
        res = [[]]
        for i in nums:
            item= []
            for j in res:
                if j + [i] not in res:
                    item =item+ [j + [i]]
            res=res+item
        return res

子集和不能超过某一个值：剪枝

class Solution:
    def combinationSum2(self, candidates: List[int], target: int) -> List[List[int]]:
        item = []
        result = []
        candidates.sort()
        sum=0
        def generate(i, candidates, item, result,sum):
            if i >= len(candidates)or sum>target:
                return
            sum += candidates[i]
            item.append(candidates[i])

            if item not in result and target==sum:
                result.append(list(item))
            generate(i + 1, candidates, item, result,sum)
            sum-=candidates[i]
            item.pop()
            generate(i + 1,candidates, item, result,sum)
        generate(0, candidates, item, result,sum)
        return result

大神版本：