[1스4코2파] # 219. LeetCode 40. Combination Sum II

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

Rule :

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

START :

[3코1파] 2023.01.04~ (219차)
[4코1파] 2023.01.13~ (211일차)
[1스4코1파] 2023.04.12~ (122일차)
[1스4코2파] 2023.05.03 ~ (100일차)

Today :

2023.08.11 [219일차]
backtracking
https://leetcode.com/problems/combination-sum-ii/

40. Combination Sum II

https://leetcode.com/problems/combination-sum-ii/

문제 설명

정수 배열 candidates 와 target 정수가 주어 질 때, candidates의 원소를 중복하지 않고 서로 조합하여 그 원소의 합이 target이 되는 subset을 return 함

문제 풀이 방법

dfs를 이용해서 backtracking 하는데 여기서 중요한건, candidates 배열을 초반에 sort를 하고, 중복 조합을 방지하기 위해서 prev라는 변수를 하나 둬서, 현재 인덱스의 다음 인덱스의 값과 일치하면 index를 건너뛰는 일련의 작업으로 수행한다.

내 코드

class Solution:
    def combinationSum2(self, candidates: List[int], target: int) -> List[List[int]]:
        candidates.sort()
        ans = []

        def dfs(idx, cur, total):
            if total > target:
                return 
            if total == target:
                ans.append(cur.copy())

            prev = -1
            for i in range(idx, len(candidates)):
                if candidates[i] == prev:
                    continue
                cur.append(candidates[i])
                dfs(i+1, cur, total+candidates[i])
                cur.pop()

                prev = candidates[i]

        dfs(0, [], 0)

        return ans

증빙

여담

수영 가야딩