Leetcode 78. Subset and 90 Subset II

78. A subset of

Give you an array of integers nums , Elements in an array Different from each other . Returns all possible subsets of the array （ Power set ）.

Solution set You can't Contains a subset of repetitions . You can press In any order Returns the solution set .

 Example  1：

 Input ：nums = [1,2,3]
 Output ：[[],[1],[2],[1,2],[3],[1,3],[2,3],[1,2,3]]

 Example  2：

 Input ：nums = [0]
 Output ：[[],[0]]

The problem of permutation , Generally, you can use deep search to do , Of course, guangsearch is also OK , Here are three solutions .

Deep search 1

Build a binary tree , Each layer determines whether to put nums[i], The path from the root node to the leaf node constitutes a subset .

class Solution:
    def subsets(self, nums: List[int]) -> List[List[int]]:
        def dfs(path, depth):
            if depth == len(nums):
                res.append(path[:])
                return 
            path.append(nums[depth])
            dfs(path, depth + 1)
            path.pop()

            dfs(path, depth + 1)
        res = []
        dfs([], 0)
        return res

Deep search 2

Each layer selects one of the remaining optional numbers to put in , From 0 Layer down , The first i A layer represents a layer containing i A subset of elements , So each layer should be saved in the answer . To avoid repetition , Sort the array first , Only select larger elements to put into （ Ensure ascending order ）.

class Solution:
    def subsets(self, nums: List[int]) -> List[List[int]]:
        def dfs(path, index):
            res.append(path[:])
            for i in range(index, len(nums)):
                path.append(nums[i])
                dfs(path, i + 1)
                path.pop()
        res = []
        nums.sort()
        dfs([], 0)
        return res

Dynamic programming

The optional numbers are different , Every time you add a number , It doubles the number of subsets that have not been added to the previous subset , So you can use dp Recurrence , From the ergodic point of view, it also looks like BFS.

class Solution:
    def subsets(self, nums: List[int]) -> List[List[int]]:
        res = [[]]
        for num in nums:
            for i in range(len(res)):
                res.append(res[i] + [num])
        return res
        

90. A subset of II

Comparison subset 1 Just one more condition , There are duplicate elements in the array , We need to do the de duplication operation . Also given dfs And dp Two kinds of solution .

dfs

In the digital selection of the same layer , There should be no duplicate elements . Therefore, if the digital selection of this layer is the same as last time , Just skip. .

class Solution:
    def subsetsWithDup(self, nums: List[int]) -> List[List[int]]:
        def dfs(path, index):
            res.append(path[:])
            for i in range(index, len(nums)):
                if i > index and nums[i - 1] == nums[i]:
                    continue
                path.append(nums[i])
                dfs(path, i + 1)
                path.pop()
        nums.sort()
        res = []
        dfs([], 0)
        return res

dp

Adopting dynamic planning still needs to be de emphasized , By sorting the same elements together , You can find , If the element to be placed this time is the same as the last time , Just add 1/2 The number of （ Otherwise, there will be repetition ）, If it is the same number last time , Increase 1/3 Subsets of , And so on .

class Solution:
    def subsetsWithDup(self, nums: List[int]) -> List[List[int]]:
        res = [[]]
        nums.sort()
        count = 2 
        for i in range(len(nums)):
            if i > 0 and nums[i - 1] == nums[i]:
                for j in range(len(res) - len(res) // count, len(res)):
                    res.append(res[j] + [nums[i]])
                count += 1
            else:
                for j in range(len(res)):
                    res.append(res[j] + [nums[i]])
                count = 2

        return res
                

It can also be used. new_subsets Record the newly added subset , The next time you encounter a duplicate element , Just in nwe_subsets On the basis of .

class Solution:
    def subsetsWithDup(self, nums: List[int]) -> List[List[int]]:
        res = [[]]
        nums.sort()
        for i in range(len(nums)):
            if i > 0 and nums[i - 1] == nums[i]:
                new_subsets = [subset + [nums[i]] for subset in new_subsets]
            else:
                new_subsets = [subset + [nums[i]] for subset in res]
            res += new_subsets
        return res