39. Combination Sum

위와 같이 candidates 안의 숫자를 이용하여 (중복 사용가능) target 숫자를 만들 수 있는 조합의 리스트를 출력하는 문제이다.

 

 

 

풀이방법

1. candidates를 오름차순으로 정렬한다.
2. 재귀함수인 recur 함수를 만들어서 숫자 조합을 만든다.
3. t보다 candidates[i]가 작으면 다음 조합으로 넘어가고 아니면 리턴한다.
4. for문은 자기 숫자부터 시작하므로 k라는 매개변수로 넘겨준다.
5.  

 

 

---

가장 중요했던 사실은 result.append(temp[:])였다.

result.append(temp)를 하면 temp주소를 넘겨주므로 이후 del temp, temp.append의 변화가 그대로 나타난다.

따라서 값 자체를 복사해주려면 [:]슬라이싱을 통해 전체를 복사해주어야 한다.

---

그래도 재귀함수를 통해 빠르게 풀 수 있어서 어려운 문제는 아니였다.

소스코드

class Solution:
    def combinationSum(self, candidates: List[int], target: int) -> List[List[int]]:
        result = []
        temp = []
        candidates.sort()        
        def recur(k,t):
            for i in range(k,len(candidates)):
                temp.append(candidates[i])
                if t == candidates[i]:
                    result.append(temp[:]) ## 리스트 값 복사 붙여넣으려면 [:]슬라이싱 필요 !!!
                    #print("***",result)
                    del temp[-1]
                    return
                elif t > candidates[i]:
                    recur(i,t - candidates[i])
                    del temp[-1]
                elif t < candidates[i]:
                    del temp[-1]
                    return
        recur(0,target)
        return result