[LeetCode] 39. Combination Sum

1. 문제

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

Combination Sum - LeetCode

2. 접근 방법

조합 내의 요소는 중복될 수 있는데, 동일한 조합이 답에 들어있으면 안됩니다.

이 말이 맞나 ?

 

그리고 해당 조합의 합이 target과 같아야합ㄴㅣ다.

 

그래서 조합을 만들어줄 때, 조합 내의 요소가 같은 조합이 여러 번 존재하지 않도록 temp에 append할 요소를 start지점에서부터 해줍니다.

근데 start 지점을 현재 idx로 해줘야합니다.

왜냐면 조합 내의 요소는 중복 가능이니까

 

3. 코드

python

class Solution:
    def combinationSum(self, candidates: List[int], target: int) -> List[List[int]]:
        def comb(s):
            if sum(temp) == target:
                answer.append(temp[:])
            elif sum(temp) < target:
                for i in range(s, len(candidates)):
                    temp.append(candidates[i])
                    comb(i)
                    temp.pop()
            return
        
        answer = []
        temp = []
        comb(0)
        return answer

4. 마치며

최근에 N과 M 시리즈를 풀이했더니 바로 보이네여

 

글구 새벽만 되면 말이 잘 안나오네여 자야겠ㅅ므다