90. Subsets II.md

90. Subsets II (Medium)

[tag] combination, DFS

• simiar as subsets, just need to sort the array and skip same numbers.

'''
[1,2,2,2]
'''
class Solution:
    def subsetsWithDup(self, nums: List[int]) -> List[List[int]]:
        ans = []
        nums.sort()
        def dfs(subset_len, s, cur_set):
            # print(subset_len, cur_set)
            if len(cur_set) == subset_len:
                print(subset_len, cur_set)
                ans.append(cur_set.copy())
                return
            # add different numbers to cur_set
            for i in range(s, len(nums)):
                if i > s:
                    if nums[i] == nums[i - 1]:
                        continue
                cur_set.append(nums[i])
                dfs(subset_len, i+1, cur_set)
                cur_set.pop()
        for subset_len in range(len(nums)+1):
            dfs(subset_len, 0, [])
        return ans

9/15

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