[Leet Code풀이] 90. Subsets 2

문제 설명

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

주어진 리스트로 부터 가능한 모든 부분 집합을 구하는 문제다. 다만 입력에 중복값이 있기 때문에 출력 값에서도 이를 잘 처리해 주어야 한다. Subset 문제 문제에 추가적인 처리를 해주었는데, 먼저

1. [4,4,4,1], [4,1,4,4] 와 같은 처리를 위해 nums 입력을 sort 하여 처리를 해주었다.
2. 중복값 처리를 따로 해주었다.

풀이

class Solution:
    def subsetsWithDup(self, nums: List[int]) -> List[List[int]]:    
        result = []

        # nums 입력을 소팅해준다.
        nums.sort()
        
        def dfs(index, path):
            # 중복값은 넣지 않는다.
            if path not in result: 
                result.append(path)
                
            for i in range(index, len(nums)):
                dfs(i+1, (path + [nums[i]]))
            
        dfs(0, [])
        
        return result