📕문제

[Leetcode] 39. Combination Sum

문제 설명

숫자 후보들로 합이 target이 되도록 하는 조합을 구하는 문제다. 이 때 각 후보들은 중복이 가능하다.

---

BackTracking

class Solution:
    def combinationSum(self, candidates: List[int], target: int) -> List[List[int]]:
        result = []

        def backTracking(prevList, total, index):
            if total == target:
                nonlocal result
                result.append(prevList)
                return
            
            for i in range(index, len(candidates)):
                if candidates[i] + total > target:
                    break
                prevList.append(candidates[i])
                backTracking(prevList, total + candidates[i], i)
                prevList.pop()
        candidates.sort()
        backTracking([], 0, 0)
        return result

backTracking()함수는 현재까지 선택한 숫자 조합을 저장한 리스트인 prevList, 현재까지 선택한 숫자의 합인 total, 다음 탐색 시작 인덱스인 index를 매개변수로 가진다.

• candidates의 시작 인덱스부터 끝까지의 숫자 중 현재까지의 합과 해당 숫자를 더했을 때 target보다 큰 경우 탐색을 중단한다.
  (candidates는 정렬이 되어있는 상태)
• 그렇지 않은 경우 prevList에 해당 숫자를 추가한 후 업데이트 된 정보로 함수를 재귀호출한다.
• 백트래킹이 끝나면 탐색을 되돌리기 위해 마지막으로 추가한 숫자를 제거한다.
• 현재까지의 합이 target이라면 result에 해당 조합을 저장한다.

코드를 실행시켜보니 이상한 현상이 발생했다.
모든 테스트케이스에 대해 조합의 개수는 맞지만 빈 배열이 들어가 있었다.
중간중간 출력해 prevList의 값을 확인했지만 result에는 빈 배열만이 존재했다.

원인은 바로 result에 prevList를 append하는 과정에 있었다.

result.append(prevList)

파이썬에서 리스트는 참조형 데이터 타입이기 때문에 prevList를 추가시킬 때 prevList의 값을 추가하는 것이 아니라 참조가 추가된다.
따라서 해당 코드를 실행시킬 때 result에 prevList의 참조가 추가되고, 이후 prevList의 내용이 변경되어 result안의 요소도 변경되게 되는것이다.

result.append(prevList[:])

prevList의 참조를 추가하는 대신 슬라이싱을 이용해 복사본을 추가하게끔 코드를 수정했다.

최종 코드

class Solution:
    def combinationSum(self, candidates: List[int], target: int) -> List[List[int]]:
        result = []

        def backTracking(prevList, total, index):
            if total == target:
                nonlocal result
                result.append(prevList[:])
                return
            
            for i in range(index, len(candidates)):
                if candidates[i] + total > target:
                    break
                prevList.append(candidates[i])
                backTracking(prevList, total + candidates[i], i)
                prevList.pop()
        candidates.sort()
        backTracking([], 0, 0)
        return result