[dp] 377. Combination Sum IV

문제

Given an array of distinct integers nums and a target integer 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.ice***.

고유한 정수 숫자와 대상 정수 대상의 배열이 지정되면 대상에 추가되는 가능한 조합 수를 반환합니다.

답이 32비트 정수로 들어갈 수 있도록 테스트 사례가 생성됩니다.

예시

Example 1:

Input: nums = [1,2,3], target = 4
Output: 7
Explanation:
The possible combination ways are:
(1, 1, 1, 1)
(1, 1, 2)
(1, 2, 1)
(1, 3)
(2, 1, 1)
(2, 2)
(3, 1)
Note that different sequences are counted as different combinations.

Example 2:

Input: nums = [9], target = 3
Output: 0

제약

• 1 <= nums.length <= 200
• 1 <= nums[i] <= 1000
• All the elements of nums are unique.
• 1 <= target <= 1000

코드

const combinationSum4 = (nums, target) => {
    const dp = Array(target + 1).fill(0)
    dp[0] = 1;
    
    for (let currTarget = 1; currTarget <= target; currTarget++) {
        nums.forEach(num => {
            const difference = currTarget - num;
            if (difference >= 0) dp[currTarget] += dp[difference];
        })
    }
    
    return dp[target]
};

풀이

아이디어: 0부터 주어진 target까지 모든 경우의 수를 dp에 저장해 놓고 이전 dp[target] 을 참조해서 현재 dp[target]을 완성시키는 것이다.

dp의 형태는

dp[0] 은 주어진 nums로 target 0을 만드는 경우의 수

dp[1] 은 주어진 nums로 target 1을 만드는 경우의 수

dp[2] 은 주어진 nums로 target 2를 만드는 경우의 수

...

이다.

이 때 nums에서 뽑은 숫자 1개를 num이라고 하자.

해당 num 으로 target을 완성시키기 위해서 target과 num 의 차이 만큼 숫자를 num 에 더해주어야 한다.

이를 difference라고 하자. 즉, difference 는 target - num 이다. 물론 difference는 양수이어야 한다.

정리하자면 difference = target - num 이므로 target = num + difference 이다.

(target = num + difference = num + target - num = target )

이 때 difference 는 다시 nums 에서 숫자들로 합쳐서 구해야하는 새로운 타겟이 된다.

그러므로 dp[difference] 를 통해 새로운 타겟인 difference 를 구하는 경우의 수를 구하면 그게 내가 구하고자 하는 원래 target의 경우의 수가 된다.

설명이 복잡하니 예시를 들어보자.

예시는 아래와 같다.

nums = [4, 1, 2], target = 5

target 5을 만들기 위해 nums에서 숫자(num)를 하나씩 뽑아보자.

4를 뽑았을 때 5를 만들기 위해서는 차이값 1이 더 필요하다.

고로 nums에서 4를 뽑았을 때 5를 만들기 위한 경우의 수는 target 1을 만드는 경우의 수와 같다.

nums의 숫자들로 target이 1을 만드는 경우에서 4라는 숫자를 추가하기만 하면 되기 때문이다.

따라서 nums의 4로 target 5를 만들기 위한 경우의 수는 dp[1]의 값과 같다.

계속해서 nums에서 숫자를 뽑아서 5를 만드는 경우의 수를 생각해보자.

2를 뽑았을 때 5를 만들기 위해서는 3이 더 필요하다. dp[3]에서 값을 가지고 온다.

1을 뽑았을 때 5를 만들기 위해서는 4가 더 필요하다. dp[4]에서 값을 가지고 온다.

따라서 dp[5]를 구하기 위해서는 dp[1] + dp[3] + dp[4]를 해주면 된다.

이렇게 최종 타겟을 구하기 위해서 이전 타겟들을 저장해놓은 dp에서 값을 가지고 오면된다.

또 이전 dp값을을 구하기 위해서 다시 이전 dp를 구해오면 된다.

따라서 target 0 부터 5까지 올리면서 앞에 타겟을 참조해서 dp를 구성해나가는 것이다.

로직을 자세히 따져보자.

// dp[target]이라할 때
// dp[0] = 1, target 0은 아무것도 고르지 않는 방법 단 한가지 경우이므로 1이다.

// dp[1]은 target이 1일 때 nums중 1을 뽑았을때만 그 target을 완성시킬수 있고 
// 1을 뽑았을 때 앞으로 숫자 0이 필요하므로 dp[0]의 값을 참조한다.

// dp[2]는 target이 2일 때 nums중 1, 2를 뽑았을 때만 target을 완성시킬수 있고
// 1을 뽑았을 때 앞으로 1이 더 필요하므로 dp[1]의 경우의 수와 같다. 따라서dp[1]을 가지고 오고
// 2을 뽑았을 때 앞으로 0이 더 필요하므로 dp[0]의 경우의 수와 같다. 따라서 dp[0]을 가지고 온다.
// 따라서 dp[2] = dp[1] + dp[0] = 1 + 1 = 2 이다.

// dp[3]는 target이 3일 때 nums중 1, 2를 뽑았을 때만 target을 완성시킬수 있고
// 1을 뽑았을 때 앞으로 2이 더 필요하므로 dp[2]의 경우의 수와 같다. 따라서 dp[2]을 가지고 오고
// 2을 뽑았을 때 앞으로 1이 더 필요하므로 dp[1]의 경우의 수와 같다. 따라서 dp[1]을 가지고 온다.
// 따라서 dp[3] = dp[2] + dp[1] = 2 + 1 = 3이다.

// dp[4]는 target이 4일 때 nums중 1, 2, 4를 뽑았을 때 target을 완성시킬수 있고
// 1을 뽑았을 때 앞으로 3이 더 필요하므로 dp[3]의 경우의 수와 같다. 따라서 dp[3]을 가지고 오고
// 2을 뽑았을 때 앞으로 2이 더 필요하므로 dp[2]의 경우의 수와 같다. 따라서 dp[2]을 가지고 오고
// 4을 뽑았을 때 앞으로 0이 더 필요하므로 dp[0]의 경우의 수와 같다. 따라서 dp[0]을 가지고 온다.
// 따라서 dp[4] = dp[3] + dp[2] + dp[0] = 3 + 2 + 1 = 6이다.

// dp[5]는 target이 5일 때 nums중 1, 2, 4를 뽑았을 때 target을 완성시킬수 있고
// 1을 뽑았을 때 앞으로 4가 더 필요하므로 dp[4]의 경우의 수와 같다. 따라서 dp[4]을 가지고 오고
// 2을 뽑았을 때 앞으로 3이 더 필요하므로 dp[3]의 경우의 수와 같다. 따라서 dp[3]을 가지고 오고
// 4을 뽑았을 때 앞으로 1이 더 필요하므로 dp[1]의 경우의 수와 같다. 따라서 dp[1]을 가지고 온다.
// 따라서 dp[5] = dp[4] + dp[3] + dp[1] = 6 + 3 + 1 = 10이다.


nums: [4, 1, 2], target: 5
(difference는 currTarget - num이다.)

currTarget: 0 -> []
cnt: 1 (초기세팅)

currTarget: 1 -> [1]
cnt: 1
유효한 difference: 0
// 0 : [] + [1]

currTarget: 2 -> [1, 1], [2]
cnt: 2
유효한 difference: 0, 1
// 0: [] + [2]
// 1: [1] + [1]

currTarget: 3 -> [1, 1, 1], [1, 2], [2, 1]
cnt: 3
유효한 difference: 1, 2
// 1: [1] + [2]
// 2: [1, 1] + [1], [2] + [1]

currTarget: 4 -> [1, 1, 1, 1], [1, 1, 2], [1, 2, 1], [2, 1, 1], [4]
cnt: 6
유효한 difference: 0, 2, 3
// 0 : [] + [4]
// 2 : [1, 1] + [2], [2] + [2]
// 3 : [1, 1, 1] + [1], [1, 2] + [1], [2, 1] + [1]

...

실제로 코드를 돌려보면 아래와 같이 진행된다.

initiated dp is [ 1, 0, 0, 0, 0, 0 ]
start!
currTarget: 1 , num: 4 , difference: -3
-----------
currTarget: 1 , num: 1 , difference: 0
👉🏻 dp[1] += dp[0], so dp[1] = 1
[ 1, 1, 0, 0, 0, 0 ]
-----------
currTarget: 1 , num: 2 , difference: -1
-----------
currTarget: 2 , num: 4 , difference: -2
-----------
currTarget: 2 , num: 1 , difference: 1
👉🏻 dp[2] += dp[1], so dp[2] = 1
[ 1, 1, 1, 0, 0, 0 ]
-----------
currTarget: 2 , num: 2 , difference: 0
👉🏻 dp[2] += dp[0], so dp[2] = 2
[ 1, 1, 2, 0, 0, 0 ]
-----------
currTarget: 3 , num: 4 , difference: -1
-----------
currTarget: 3 , num: 1 , difference: 2
👉🏻 dp[3] += dp[2], so dp[3] = 2
[ 1, 1, 2, 2, 0, 0 ]
-----------
currTarget: 3 , num: 2 , difference: 1
👉🏻 dp[3] += dp[1], so dp[3] = 3
[ 1, 1, 2, 3, 0, 0 ]
-----------
currTarget: 4 , num: 4 , difference: 0
👉🏻 dp[4] += dp[0], so dp[4] = 1
[ 1, 1, 2, 3, 1, 0 ]
-----------
currTarget: 4 , num: 1 , difference: 3
👉🏻 dp[4] += dp[3], so dp[4] = 4
[ 1, 1, 2, 3, 4, 0 ]
-----------
currTarget: 4 , num: 2 , difference: 2
👉🏻 dp[4] += dp[2], so dp[4] = 6
[ 1, 1, 2, 3, 6, 0 ]
-----------
currTarget: 5 , num: 4 , difference: 1
👉🏻 dp[5] += dp[1], so dp[5] = 1
[ 1, 1, 2, 3, 6, 1 ]
-----------
currTarget: 5 , num: 1 , difference: 4
👉🏻 dp[5] += dp[4], so dp[5] = 7
[ 1, 1, 2, 3, 6, 7 ]
-----------
currTarget: 5 , num: 2 , difference: 3
👉🏻 dp[5] += dp[3], so dp[5] = 10
[ 1, 1, 2, 3, 6, 10 ]
-----------
res : [ 1, 1, 2, 3, 6, 10 ]

코드의 진행상황을 보이기 위해 작성한 코드

const combinationSum4 = (nums, target) => {
    const dp = Array(target + 1).fill(0)
    dp[0] = 1
    
    console.log('initiated dp is', dp);
    console.log('start!')
    for (let currTarget = 1; currTarget <= target; currTarget++) {
        nums.forEach(num => {
            const difference = currTarget - num;
            console.log('currTarget:', currTarget, ', num:', num, ', difference:', difference);
            if (difference >= 0) {
                dp[currTarget] += dp[difference];
                console.log(`👉🏻 dp[${currTarget}] += dp[${difference}], so dp[${currTarget}] = ${dp[currTarget]}`);
                console.log(dp);                
            }
            console.log('-----------');
        })
    }
    
    console.log('res :', [...Array(5)].map((_, i) => i));
    return dp[target]
};

다른 케이스

nums: [1, 2, 3], target: 4

target 0 -> []
cnt: 1;

target 1 -> [1]
cnt: 1;
유효한 difference: 0
[] + [1]

target 2 -> [1, 1], [2]
cnt: 2
유효한 difference: 0, 1
0 : [] + [2]
1 : [1] + [1]

target 3 -> [1, 1, 1], [2, 1], [1, 2], [3]
cnt: 4
유효한 difference: 0, 1, 2
0 : [] + [3]
1 : [1] + [2]
2 : [1, 1] + [1], [2] + [1]

target 4 -> [1, 1, 1, 1], [2, 1, 1], [1, 2, 1], [1, 1, 2], [2, 2], [3, 1], [1, 3]
cnt: 4
유효한 difference: 1, 2, 3
1 : [1] + [3]
2 : [1, 1] + [2], [2] + [2]
3 : [1, 1, 1] + [1], [2, 1] + [1], [1, 2] + [1], [3] + [1]

최종 dp = [1, 1, 2, 4, 7];

코드 진행

initiated dp is [ 1, 0, 0, 0, 0 ]
start!
currTarget: 1 , num: 1 , difference: 0
👉🏻 dp[1] += dp[0], so dp[1] = 1
[ 1, 1, 0, 0, 0 ]
-----------
currTarget: 1 , num: 2 , difference: -1
-----------
currTarget: 1 , num: 3 , difference: -2
-----------
currTarget: 2 , num: 1 , difference: 1
👉🏻 dp[2] += dp[1], so dp[2] = 1
[ 1, 1, 1, 0, 0 ]
-----------
currTarget: 2 , num: 2 , difference: 0
👉🏻 dp[2] += dp[0], so dp[2] = 2
[ 1, 1, 2, 0, 0 ]
-----------
currTarget: 2 , num: 3 , difference: -1
-----------
currTarget: 3 , num: 1 , difference: 2
👉🏻 dp[3] += dp[2], so dp[3] = 2
[ 1, 1, 2, 2, 0 ]
-----------
currTarget: 3 , num: 2 , difference: 1
👉🏻 dp[3] += dp[1], so dp[3] = 3
[ 1, 1, 2, 3, 0 ]
-----------
currTarget: 3 , num: 3 , difference: 0
👉🏻 dp[3] += dp[0], so dp[3] = 4
[ 1, 1, 2, 4, 0 ]
-----------
currTarget: 4 , num: 1 , difference: 3
👉🏻 dp[4] += dp[3], so dp[4] = 4
[ 1, 1, 2, 4, 4 ]
-----------
currTarget: 4 , num: 2 , difference: 2
👉🏻 dp[4] += dp[2], so dp[4] = 6
[ 1, 1, 2, 4, 6 ]
-----------
currTarget: 4 , num: 3 , difference: 1
👉🏻 dp[4] += dp[1], so dp[4] = 7
[ 1, 1, 2, 4, 7 ]
-----------
res : [ 1, 1, 2, 4, 7 ]

도움이 되는 참고자료
https://dev.to/seanpgallivan/solution-combination-sum-iv-3620
https://medium.com/@peteryun/algo-leetcode-combination-sum-iv-a04f10ef0794
https://www.youtube.com/watch?v=GWqe_xfqxCA