[1스4코2파] # 218. LeetCode 90. Subsets II

[1스4코2파] 1명의 스위프트 개발자와 4명의 코틀린 개발자, 2명의 파이썬 개발자코딩 테스트 서막 : 1스4코1파

Rule :

하루에 1문제씩 풀기.
한 문제당 30분씩은 고민하기.
왜 그렇게 풀었는지 공유하기.
하루라도 놓친다면 벌금은 1,000원
백준 플래티넘, 프로그래머스 4단계, 개발자 탈퇴 시 모임 탈퇴 가능

START :

[3코1파] 2023.01.04~ (218차)
[4코1파] 2023.01.13~ (210일차)
[1스4코1파] 2023.04.12~ (121일차)
[1스4코2파] 2023.05.03 ~ (99일차)

Today :

2023.08.10 [218일차]
backtracking
https://leetcode.com/problems/subsets-ii/

90. Subsets II

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

문제 설명

중복을 포함한 정수 배열 nums가 주어질때, 배열 안의 원소로 조합한 하위집합을 반환한다. 해당 하위 집합은 중복된 하위 집합을 포함하지 않고 return 함

문제 풀이 방법

주어진 정수배열이 중복을 포함하고 있으므로, sort를 먼저 꼭 해주고
dfs 를 돌면서, dfs 내에서 정수 배열이 연속적으로 같은 숫자일 경우에 while문을 통해서 빠져나온 뒤에 인덱스에 +1을 해줘서 배열의 다음의 원소를 하위집합의 요소로 넣어줌

내 코드

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

        def dfs(idx, cur):
            if idx == len(nums):
                ans.append(cur.copy())
                return

            cur.append(nums[idx])
            dfs(idx+1, cur)
            cur.pop()           
            while idx+1 < len(nums) and nums[idx+1] == nums[idx]:
                idx+=1

            
            dfs(idx+1, cur)

        dfs(0, [])
        return ans

증빙

여담

훈장님이 옆에서 훈수 두면서 같이 풀어서 오늘 다시 혼자서 풀어서 복습 완