78.子集

link
给你一个整数数组 nums ，数组中的元素互不相同。返回该数组所有可能的子集（幂集）。解集不能包含重复的子集。你可以按任意顺序返回解集。

思路

如果把子集问题、组合问题、分割问题都抽象为一棵树的话，那么组合问题和分割问题都是收集树的叶子节点，而子集问题是找树的所有节点。

只需要在回溯函数中每次都添加当前结果即可，注意可以不添加终止函数。

class Solution:
    def subsets(self, nums: List[int]) -> List[List[int]]:
        res = []
        cur = []

        def backtrack(start):
            res.append(cur[:])
            # if start == len(nums):
            #     return

            for i in range(start, len(nums)):
                cur.append(nums[i])
                backtrack(i + 1)
                cur.pop()
            
        backtrack(0)
        return res

90.子集II

link

和上一题类似，只不过给定的 nums 可能包含重复元素

思路

直接用上一题的代码会重复选择某些元素，解决方法可以是先将数据进行排序，然后判断当前元素和前一个选择的元素是否相等，如果相等则跳过。

class Solution:
    def subsetsWithDup(self, nums: List[int]) -> List[List[int]]:
        res = []
        cur = []
        nums.sort()
        def backtrack(start):
            res.append(cur[:])
            # if start == len(nums):
            #     return
            pre = None
            for i in range(start, len(nums)):
                if pre == None or pre != nums[i]:
                    cur.append(nums[i])
                    backtrack(i + 1)
                    pre = cur.pop()
                
        backtrack(0)
        return res

更正确（？）的写法，分清楚树枝和树层之间的关系，使用一个 used 数组，如果当前数字和前一个数字相同，并且前一个数字已经 used，说明当前层已经用过该数字，需要跳过。

used[i - 1] == true，说明同一树枝 candidates[i - 1]使用过
used[i - 1] == false，说明同一树层 candidates[i - 1]使用过
而我们要对同一树层使用过的元素进行跳过

注意需要动态更新 used 数组。

class Solution:
    def subsetsWithDup(self, nums: List[int]) -> List[List[int]]:
        res = []
        cur = []
        used = [False] * len(nums)
        nums.sort()
        def backtrack(start):
            res.append(cur[:])
            
            for i in range(start, len(nums)):
                if i != 0 and used[i - 1] == False and nums[i] == nums[i-1]:
                    continue
                cur.append(nums[i])
                used[i] = True
                backtrack(i + 1)
                used[i] = False
                cur.pop()
                     
        backtrack(0)
        return res