[LeetCode] Combination Sum

문제링크

Combination Sum - LeetCode

 

정수 배열 candidates가 주어지고 target 값이 주어질때
candidates의 element를 통해 target을 만들 수 있는 모든 경우를 배열에 담아 return 하는 문제이다.

조건 : candidates의 element는 중복으로 사용할 수 있다.

candidates = [2,3,6,7], target = 7인 경우
return [[2,2,3], [7]]

접근 방법

dp를 사용하여 풀이하였다.

target + 1길이의 dp를 빈 배열로 초기화하고 dp[0]을 빈 배열을 갖는 2차 배열로 초기화 하였다.

const dp = Array.from({length : target+1}, () => [])
    
dp[0] = [[]];​

cadidates를 순회하며 dp[n - candidate]이 존재 할 경우 dp[n]에 dp[n-candidate].concat([candidate])를 추가하는 방식으로 진행하였다.
(즉, candidate = 2일때, dp[4]는 dp[2]가 존재하는 경우 dp[4].push(dp[2].concat([2])) 를 한다.)

candidates.forEach(candidate => {
    for(let i = candidate; i <= target; i++) {
        dp[i - candidate].forEach(combination => {
            dp[i].push(combination.concat([candidate]));
        })
    }
})

candidates = [2,3,6,7], target = 7인 경우

위의 로직으로 진행하면

candidate = 2일때
[ [ [] ], [], [], [], [], [], [], [] ] =>
[ [ [] ], [], [ [ 2 ] ], [], [], [], [], [] ] =>
[ [ [] ], [], [ [ 2 ] ], [], [ [ 2,2 ] ], [], [], [] ] =>
[ [ [] ], [], [ [ 2 ] ], [], [ [ 2, 2 ] ], [], [ [ 2, 2, 2 ] ], [] ]

candidate = 3일때
[ [ [] ], [], [ [ 2 ] ], [], [ [ 2, 2 ] ], [], [ [ 2, 2, 2 ] ], [] ] =>
[ [ [] ], [], [ [ 2 ] ], [ [ 3 ] ], [ [ 2, 2 ] ], [], [ [ 2, 2, 2 ] ], [] ] =>
[ [ [] ], [], [ [ 2 ] ], [ [ 3 ] ], [ [ 2, 2 ] ], [ [ 2, 3 ] ], [ [ 2, 2, 2 ] ], [] ] =>
[ [ [] ], [], [ [ 2 ] ], [ [ 3 ] ], [ [ 2, 2 ] ], [ [ 2, 3 ] ], [ [ 2, 2, 2 ], [ 3, 3 ] ], [] ] =>
[ [ [] ], [], [ [ 2 ] ], [ [ 3 ] ], [ [ 2, 2 ] ], [ [ 2, 3 ] ], [ [ 2, 2, 2 ], [ 3, 3 ], [ [ 2, 2, 3 ] ] ]

방식으로 진행되어 최종적으로 아래의 결과를 얻는다.
[ [ [] ], [], [ [ 2 ] ], [ [ 3 ] ], [ [ 2, 2 ] ], [ [ 2, 3 ] ], [ [ 2, 2, 2 ], [ 3, 3 ], [ 6 ] ], [ [ 2, 2, 3 ], [ 7 ] ] ]


핵심 부분은 아래의 코드인데

dp[i - candidate].forEach(combination => {
    dp[i].push(combination.concat([candidate]));
})

dp[i - candidate] 가 존재할 경우에만 dp[i]에 추가하는 것이고 dp[i - candidate]가 존재하지 않으면 forEach문이 실행되지 않는다.

/**
 * @param {number[]} candidates
 * @param {number} target
 * @return {number[][]}
 */
var combinationSum = function(candidates, target) {
    const dp = Array.from({length : target+1}, () => [])
    
    dp[0] = [[]];
    
    candidates.forEach(candidate => {
        for(let i = candidate; i <= target; i++) {
            dp[i - candidate].forEach(combination => {
                dp[i].push(combination.concat([candidate]));
            })
        }
    })
    
    return dp[target];
}