ch12-5(leetcode 39). 조합의 합

* 해당 포스트는 <파이썬 알고리즘 인터뷰> 공부 후 정리 목적으로 작성되었습니다. *

 

leetcode 39번 ( https://leetcode.com/problems/combination-sum/ )

 

풀이 1. (교재 참고)

중첩 함수(nested function)를 선언하고 그 함수를 재귀적으로 호출하면 풀 수 있다. 

 

주어진 배열 candidates의 각 원소를 횟수 제한 없이 사용해서 정확히 target의 값을 만드는 문제이다. 

unbounded knapsack 문제와도 유사하다. 

 

예를 들어 candidates = [2, 3, 4], target = 7인 상황에서 맨 처음 2를 선택했다고 해 보자. 

이 경우 각 원소를 한 번만 써야하는 것이 아니므로 똑같이 [2, 3, 4]의 값을 사용해서 7-2인 5를 만들어 내면 되는 문제를 풀면 된다. 

 

즉 candidates[] 배열에서 target T를 만드는 문제에서 candidates의 i번째 원소인 candidates[i]를 선택한다고 가정하면, 이 문제는 candidates[] 배열에서 T-candidates[i] 만큼의 값을 만드는 문제와 같아진다. 

이를 재귀 함수를 호출하는 방식으로 풀 수 있다. 

def combinationSum(self, candidates, target):
    result = []
	
    # recursion function
    def dfs():
        # function

 

그리고 이 문제는 combination sum이기 때문에 순열처럼 하나의 경우의 수에 들어있는 원소의 순서를 고려하지 않는다. 순열이 아니라 조합 문제이다. 

그렇기 때문에 이전의 조합 문제에서처럼 앞의 원소가 조합에 포함된 경우를 이미 계산했다면, 그 다음부터는 뒤의 원소들만 조합에 포함된다고 가정하고 계산하면 된다. 

 

예를 들어 [A1, A2, A3, A4, A5] 원소를 가지고 3개를 선택하는 조합을 만든다고 해 보자. (combinations(5, 3) = 5C3)

여기서 A1이 선택되는 경우만 계산하면 [A1, A2, A3], [A1, A2, A4], [A1, A2, A5], [A1, A3, A4], [A1, A3, A5], [A1, A4, A5] 다음과 같다. 

5개의 원소를 중 3개를 조합으로 뽑는 경우는 총 10개이고, 나머지 경우는 [A2, A3, A4], [A2, A3, A5], [A2, A4, A5], [A3, A4, A5]이다. 나머지 경우에는 모두 A1이 포함되지 않는다. 

combination sum도 조합이므로 한 원소가 포함되는 경우를 이미 계산하면 그 다음부터는 그 다음에 오는 원소들만 포함한다고 가정할 수 있다. 

 

그러므로 재귀함수 dfs()는 원소를 더해서 완성해야 할 값(csum)뿐만 아니라 어느 원소부터 조합에 포함시킬지(index)도 매개변수로 받아야 한다. 

그리고 dfs()를 호출할수록 원소가 추가되므로, 해당 원소들의 값을 저장해 두었다가 후에 결과(results)에 추가하기 위해서는 각 재귀 호출마다 현재 target을 만들기 위해 저장된 값 리스트(path)도 매개변수로 넘겨 주어야 한다. 

def dfs(csum, index, path):

 

그러나 이렇게만 가정하면 계속해서 합이 늘어나는 무한루프에 갇히게 된다. 재귀함수를 사용할 때는 반드시 재귀를 멈추는 조건인 base case를 명시해 주어야 한다. 

문제에서는 원소를 더했을 때 target 값과 정확히 일치해야 하므로, target 값과 일치하면 결과에다 더하고, target 값을 초과했다면 그냥 종료(return)시켜야 한다. 

# base case
if total < 0:
    return
elif total == 0:
    result.append(path)
    return
    
# recursion case

 

교재에서 제시한 풀이를 보면 중첩 함수 dfs()는 어떤 값을 리턴하지는 않는다. 다만 result라는 결과 변수는 dfs() 함수 밖과 정답 함수(combinationSum) 안에 선언된 로컬 변수이므로, dfs()에서 result에 값을 추가하면 로컬 변수인 result에도 그 결과가 반영된다. 

따라서 결과 변수 result를 그대로 리턴하면 된다. 

 

하지만 주의할 점은, 외부 함수 안에서 선언된 로컬 변수의 값을 중첩 함수 안에서 변경한다고 해서 그 외부 로컬변수의 값이 항상 변경되지는 않는다는 것이다. 

앞서 result의 값이 변경된 이유는 result는 리스트 형식이라서 값이 변경될 수 있는 가변 객체(mutable object)이기 때문이다. 리스트와 달리 값이 변경될 수 없는 객체(immutable object)인 문자열 등의 경우 중첩 함수에서 값을 바꾸려고 시도하면 값이 바뀌지 않고, 해당 중첩 함수에서만 사용할 수 있는 새로운 로컬 변수가 된다. 

 

 

참고한 포스트

https://www.geeksforgeeks.org/unbounded-knapsack-repetition-items-allowed/