[LeetCode] Combination Sum IV

문제링크

 

주어진 정수 배열 nums의 요소들을 사용하여 target을 만드는 방법의 수를 구하는 문제
각 요소들은 중복으로 사용할 수 있고 순열 방식을 따른다. (1,3)과 (3,1)을 다른 경우로 봄

접근 방법

전형적인 dp문제로 이번 dp의 핵심은 dp[n] => n을 만들 수 있는 경우의 수란 점이다.

1 ~ target까지 dp[n]을 구하고 (dp[1] === 1을 만들 수 있는 경우의 수, dp[2] === 2를 만들 수 있는 경우의 수...)

만약 dp[5]를 구하는데 현재 num은 2이고, dp[3]을 만드는 방법이 3개라면 
dp[5] += dp[5 - 2] 라는 개념이 가능할 것 이다. (dp[3]을 만드는 방법이 3개고, 현재 num은 2이므로 dp[5]에도 3가지 방법이 추가될 수 있다.)

for(let curTarget = 1; curTarget <= target; curTarget++){
    for(let num of nums){
        if((curTarget - num) >= 0){
            if(curTarget === num){
                dp[curTarget] += 1;
            }else{
                dp[curTarget] += dp[curTarget - num];
            }
        }
    }
}​

코드로 구현하면 이렇게 된다.

curTarget은 1 ~ target까지 순회하며 현재 값을 target이라 생각하겠다는 의미의 변수이고

curTarget이 nums의 원소보다 작다면 가능하지 않은 경우이므로 다음 for문으로 넘어간다.

또한 dp[curTarget]인 경우는 단순하게 1을 추가해주고,
앞서 살펴본대로 만약 curTarget - num >= 0이고, curTarget !== num인 경우 dp[curTarget] += dp[curTarget - num]을 추가해준다. 

 

/**
 * @param {number[]} nums
 * @param {number} target
 * @return {number}
 */
var combinationSum4 = function(nums, target) {
    const dp = new Array(target + 1).fill(0);
    dp[0] = 0;
    
    for(let curTarget = 1; curTarget <= target; curTarget++){
        for(let num of nums){
            if((curTarget - num) >= 0){
                if(curTarget === num){
                    dp[curTarget] += 1;
                }else{
                    dp[curTarget] += dp[curTarget - num];
                }
            }
        }
    }
    return dp[target]
};