Daily Leetcoding Challenge 377. Combination Sum IV

주말에도 한 문제. 식은 도출했지만... 마무리가 아쉬웠던 문제

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

Combination Sum IV - LeetCode

직관

이 문제에서는 숫자 순서가 다르면 다른 조합으로 인정하기 때문에 주어진 배열로 target을 만들 수 있는 모든 순열을 찾아야 한다. 그리고 nums 배열의 숫자를 반복해서 사용할 수 있는 점도 참고해야 한다. 재귀적으로 문제를 푼다면 target을 만들 수 있는 순열의 수는 target - nums[i] (0 <= i < nums.length)가 0보다 크거나 같을 때 target - nums[i]를 만들 수 있는 순열의 수의 합이 된다.

정리하면, combinationSum4(target) = sum(combinationSum4(target - nums[i]) where target - nums[i] >= 0이다. 그리고 베이스케이스는 combinationSum4(0)이 될 텐데, target의 값으로 0이 주어지지는 않지만, 이 재귀식에서 combinationSum4(0)은 target과 nums[i]의 값이 같은 경우를 의미하고 그때는 1가지 순열뿐이므로 combinationSum4(0)를 1로 정의한다. 

접근법

combinationSum4(target) = sum(combinationSum4(target - nums[i]) where target - nums[i] >= 0 식을 이용해서 재귀적으로 문제를 먼저 풀고, 그 뒤에 메모이제이션(memoization)을 이용해서 top-down 방식으로 문제를 풀어보고, 그 뒤에 bottom-up으로 문제를 풀어본다.

복잡도

nums 배열의 크기를 N, target을 간단히 T라고 하자.

재귀함수로 문제를 푸는 경우 시간 복잡도는 O(N^T)가 된다. 공간 복잡도는 재귀 함수의 스택이 최대 T가 될 수 있으므로 O(T)가 된다.

Top-down 접근법의 경우 부분 문제를 저장하는 공간이 T+1만큼 할당된다. 그리고 재귀함수의 스택도 최대 T가 될 수 있으므로 공간 복잡도는 O(T)다. 그리고 시간 복잡도는 O(N * T)가 된다.

(top down 방식이 메모이제이션을 사용하기 때문에 시간 복잡도가 줄어드는 건 맞는데 직관적으로 이해는 잘 안되는 것 같다.)

코드

재귀

class Solution {
    public int combinationSum4(int[] nums, int target) {
        if (target == 0) {
            return 1;
        }
        int ret = 0;
        for (int i=0; i < nums.length; i++) {
            if (target >= nums[i]) {
                ret += combinationSum4(nums, target - nums[i]);
            }
        }
        return ret;
    }
}

Top-down DP

class Solution {
    public int combinationSum4(int[] nums, int target) {
        int[] dp = new int[target+1];
        Arrays.fill(dp, -1);
        dp[0] = 1;
        return helper(nums, target, dp);
    }

    private int helper(int[] nums, int target, int[] dp) {
        if (dp[target] != -1) {
            return dp[target];
        }

        int ret = 0;
        for(int i=0; i<nums.length; i++) {
            if (target >= nums[i]) {
                ret += helper(nums, target - nums[i], dp);
            }
        }
        dp[target] = ret;
        return dp[target];
    }
}

Bottom-up DP

class Solution {
    public int combinationSum4(int[] nums, int target) {
        int[] dp = new int[target+1];
        dp[0] = 1;
        for(int i=1; i<dp.length; i++) {
            for(int j=0; j<nums.length; j++) {
                if (i - nums[j] >= 0) {
                    dp[i] += dp[i - nums[j]];
                }
            }
        }
        return dp[target];
    }
}