[Leetcode 90] - Subsets II

 

 

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.

 

 

 

중복된 숫자가 있는 배열이 주어졌을때 가능한 하위 집합을 찾는 문제

리턴하는 배열에는 중복된 집합을 포함시킬수 없다

 

 

 

https://leetcode.com/problems/subsets-ii/description/

 

 

 

---

 

 

 

Example 1:

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

 

 

 

Example 2:

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

 

 

 

---

 

 

 

백트래킹으로 배열을 확인하면서 풀 수 있는 문제

 

1. 배열 정렬을 함으로써 중복된 숫자를 빠르게 없앨수 있다

2. index가 nums의 길이에 도달했을때 ans에 저장

3. 2가지의 백트래킹을 해야된다:

※ 모든 숫자를 포함한 경우 - [1, 2, 2]

※ 중복된 숫자를 없애고 현재 숫자를 포함시키지 않는 경우 [1, 2], [2, 2], [1], [2], []

 

이해 도움 되는 사진 만듬

 

class Solution:
    def subsetsWithDup(self, nums):
        ans = []
        nums.sort()

        def backtrack(start, stack):
            if start == len(nums):
                ans.append(stack.copy())
                return
            
            stack.append(nums[start])
            backtrack(start + 1, stack)
            stack.pop()
			
            # 다음 숫자가 현재 숫자랑 같다면 다음 숫자로 넘어가기 (중복된 숫자 방지)
            while start + 1 < len(nums) and nums[start] == nums[start+1]:
                start += 1 
            backtrack(start + 1, stack)
            return
        
        backtrack(0, [])
        return ans