[1스4코2파] # 216. LeetCode 39. Combination Sum

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

Rule :

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

START :

[3코1파] 2023.01.04~ (216차)
[4코1파] 2023.01.13~ (208일차)
[1스4코1파] 2023.04.12~ (119일차)
[1스4코2파] 2023.05.03 ~ (97일차)

Today :

2023.08.08 [216일차]
backtracking
https://leetcode.com/problems/combination-sum/

39. Combination Sum

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

문제 설명

int형 원소를 가지고 있는 배열과 target이 주어졌을 때,
해당 배열의 원소의 조합의 합으로 target이 만들어지면
해당 배열의 원소들의 조합을 return 하는 것

문제 풀이 방법

backtracking을 이용하는데 현재 리스트, 리스트의 합 인 total, 현재 인덱스 세 값을 이용해서 풀어줌...
배열 원소가 중복이 가능하기 때문에
i, cur, total+현재값 과 그 이후에 cur를 pop 해준 후에 i+1로 넘어가는 것이 중요함

내 코드

class Solution:
    def combinationSum(self, candidates, target: int):
        ans = []
        
        def dfs(i, cur, total):
            if total == target:
                ans.append(cur.copy())
                return
            
            if i >= len(candidates) or total > target:
                return 
            
            cur.append(candidates[i])
            dfs(i, cur, total+candidates[i])
            cur.pop()
            dfs(i+1, cur, total)
            
        dfs(0, [], 0)
        
        return ans

증빙

여담