[ leetcode 문제풀이 ] Combination Sum IV

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

Combination Sum IV - LeetCode

(Combination Sum IV 문제는 위 링크에서 풀어보실 수 있습니다.)

< Combination Sum IV 문제 설명 >

Combination Sum IV 문제는 다음과 같다.

Given an array of distinct integers nums and a target integers target, return the number of possible combinations that add up to target.

The test cases are generated so that the answer can fit in a 32-bit integer.

 

서로 다른 정수 배열 array와 목표 정수 target이 주어졌을 때 array의 원소를 더해 target을 만들 수 있는 조합의 수를 리턴하여라.

다음 두 가지 출력 예시가 주어졌다.

주어진 제한 조건은 1 ≤ nums.length ≤ 200, 1 ≤ nums[i] ≤ 1000, 1 ≤ target ≤ 1000 과 nums에는 중복되는 원소가 없다는 것이고, follow up question으로는 만약 음수도 array의 원소가 될 수 있다고 하면 이는 문제를 어떻게 바꿀 것인가? 음수를 허용하기 위해서는 어떤 제한 조건을 문제에 추가해야 할 것인가? 이다.

 

---

< Combination Sum IV 문제 접근>

combination sum IV 문제는 간단한 점화식 형태로 관계를 나타낼 수 있다. 문제에서 주어준 1번째 출력 예시를 통해 알아보자.

Input으로 주어준 nums = [1, 2, 3]과 target = 4에 대해서 combination sum답을 출력하는 함수를 CombinationSum(target)이라 해보자.(nums는 알고 있다 치고 생략)
더하는 첫 번째 수를 nums의 첫 번째 원소 1로 정하면 남은 숫자 조합을 정하는 문제는 CombinationSum(3)을 구하는 것과 같다.
같은 방법으로 더하는 두 번째, 세 번째 수를 nums의 두 번째, 세 번째 원소인 2와 3으로 정했을 경우의 부분 문제는 CombinationSum(2)와 CombinationSum(1)이다.

한편, target을 만드는 원소의 순서 역시 고려대상이므로 세 부분문제는 서로 배반사건이다. 즉,

CombinationSum(4) = CombinationSum(3) + CombinationSum(2) + CombinationSum(1)

이라는 관계가 성립한다. (앞으로 남은 선택들에 대한 해답으로 부분 문제를 정의하였으며 중복될 수 있는 부분 문제가 많이 생기도록 한 꼴임 - 최적화 문제 동적 계획법 레시피 참고)

이 관계식을 일반적인 형태로 나타내면 다음과 같다.

CombinationSum(target) = CombinationSum(target - nums[0]) + ... + CombinationSum(target - nums[-1])

물론 이 관계식은 어디까지나 target - nums[i]가 음이 아닌 정수라고 가정했을 때 성립하기에, CombinationSum 함수의 매개변수 target이 0일때와 음수일 때의 경계조건을 고려하면 아래 코드와 같이 나타낼 수 있다. (Cpp사용)

int cache[1001];
std::fill_n(cache, 1001, -1);
cache[0] = 1;

int combinationSum4(vector<int>& nums, int target){
    if(target<0) return 0;
    
    int& ret = cache[target];
    if(ret != -1) return ret;			// 메모이제이션 적용

    ret = 0;
    for(int i=0;i<nums.size();i++)
        ret += combinationSum4(nums, target - nums[i]);
    return ret;
} // top-down approach

>> run combinationSum4(nums, target)

맨 처음 알고리즘을 짤 때는 위와 같이 top-down 방식을 사용했다. 근데 이렇게 구성한 코드는 leetcode에 작성하기 조금 불편한(?) 형태라 bottom-up 방식의 코드도 작성해 보았다.

 

int combinationSum4(vector<int>&nums, int target){
    vector<uint32_t> cache(target+1);
    cache[0] = 1;

    for(int i=1;i<=target;i++)
        for(int j=0;j<nums.size();j++)
            if(i-nums[j] >= 0)
                cache[i] += cache[i-nums[j]];
    return cache[target];
} // bottom-up approach

 

Submission Detail을 비교해보면 bottom-up approach는 Runtime: 4 ms, Memory Usage: 6.6 ms이고 top-down approach는 Runtime: 3 ms, Memory Usage: 6.7 ms이다. 메모리 사용량은 거의 차이가 없고, runtime에서 top-down 방식이 더 빨랐다. 이유를 생각해보자면 bottom-up 방식은 0 ~ target까지의 경우에 대한 모든 부분 문제에 대한 탐색을 진행하지만, top-down 방식은 필요한 부분 문제만 선택적으로 탐색하기에 나타나는 차이로 추정된다.

 

이 외에 코드를 구현하면서 두 방식의 차이점이라 느낀 것은 top-down 방식은 부분 문제만 잘 정의하면 recursion을 통해 직관적으로 코드를 작성할 수 있었다. 반면 bottom-up 방식은 top-down 방식보다 예외조건 등의 처리가 까다롭다고 느꼈다. 하지만 이 역시 문제별로, 조건별로 어떤 방식이 더 구현하기 쉬운지 다르기에 상황별로 적절한 접근 방식을 사용하는 것이 필요해 보인다.