90. Subsets II

Problem Statement

link: LeetCode.cn LeetCode

Given an integer array nums that may contain duplicates, return all possible subsets (the power set).

The solution set must not contain duplicate subsets. Return the solution in any order.

Example:

Input: nums = [1,2,2] Output: [[],[1],[1,2],[1,2,2],[2],[2,2]]

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

Solution Approach

The solution employs backtracking to generate all possible subsets, ensuring no duplicate sets are created by sorting the array and skipping over consecutive duplicate elements.

Algorithm

1. Begin by sorting the given nums array to ensure duplicates are adjacent.
2. Implement the backtrack function, which appends the current subset to the result and then recursively explores possible extensions of this subset.
3. While iterating through the numbers, skip over duplicates by checking if the current number is the same as the previous, ensuring no repeated subsets are added.

Implement

    class Solution:
      def subsetsWithDup(self, nums: List[int]) -> List[List[int]]:
        nums.sort()
        res = []
        l = len(nums)
        if not l:
            return res

        def backtrack(path, step):
            res.append(path)
            for i in range(step, l):
                if step < i and nums[i] == nums[i - 1]: # here should be step < i and nums[i] == nums[i - 1]
                    continue
                else:
                    backtrack(path + [nums[i]], i + 1) # here should be nums[i] and i + 1

        backtrack([],0)
        return res


 

    
    

Twitter  facebook  Email