문제링크
Combination Sum - LeetCode
Level up your coding skills and quickly land a job. This is the best place to expand your knowledge and get prepared for your next interview.
leetcode.com
정수 배열 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];
}
'코딩테스트 > LeetCode' 카테고리의 다른 글
[LeetCode] Single Number II (0) | 2022.07.15 |
---|---|
[LeetCode] Matchsticks To Square (0) | 2022.07.12 |
[LeetCode] Min Cost Climbing Stairs (0) | 2022.07.10 |
[LeetCode] Single Number (0) | 2022.07.09 |
[LeetCode] Fibonacci Number (0) | 2022.07.06 |