-
[75 LeetCode] 39 - Combination Sum IVStudy/Leetcode 2023. 5. 28. 16:00
[75 LeetCode]는 코딩테스트 연습을 위해 한 페이스북 개발자가 추천하는 75가지 알고리즘 문제를 풀어보는 시리즈이다.
블라인드 원문:
https://www.teamblind.com/post/New-Year-Gift---Curated-List-of-Top-75-LeetCode-Questions-to-Save-Your-Time-OaM1orEU문제 링크: https://leetcode.com/problems/combination-sum-iv/description/
Combination Sum IV - LeetCode
Can you solve this real interview question? 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 fi
leetcode.com
주어진 예시는 다음과 같았다.
처음에 고민하다 위 예시를 보고 실마리를 찾았다.
4를 만드는 경우의 수가 나열되어 있는데, 맨 앞자리와 나머지 자리를 분리해서 살펴보면
1 - 1, 1, 1 1 - 1, 2 1 - 2, 1 1 - 3 2 - 1, 1 2 - 2 3 - 1
위와 같다.
위 예제에서는 다음과 같은 규칙을 찾을 수 있다.
1) 4를 만들기 위해 맨 앞자리에 1을 쓰는 경우의 수는 맨 앞자리에 1을 넣고 나머지로 3을 만드는 경우의 수와 같다.
2) 2와 3의 경우도 마찬가지이다.
3) 즉, 4를 만들기 위해선
(맨 앞자리가 1인 경우 3을 만드는 경우의 수)
+ (맨 앞자리가 2인 경우 2를 만드는 경우의 수)
+ (맨 앞자리가 3인 경우 1을 만드는 경우의 수)
만큼의 경우의 수가 필요하다.조금 더 일반화하면 다음과 같다.
nums의 원소로 t을 만드는 경우의 수를 f(t)라 하자.
f(t) = Sum(for num in nums; f(t - num))
위 공식을 통해 dp를 시도해보면 다음과 같다.
var combinationSum4 = function(nums, target) { const dp = [...Array(target + 1)].fill(0); dp[0] = 1; nums.sort((a, b) => Number(a) - Number(b)); for (let i = 1; i <= target; i++) { for(let j = 0; i - nums[j] >= 0; j++) { dp[i] += dp[i - nums[j]]; } } return dp[target]; };
i는 target까지 dp를 채우기 위한 순회, j는 각 nums에 대한 순회다.
728x90'Study > Leetcode' 카테고리의 다른 글
[75 LeetCode] 41 - House Robber 2 (0) 2023.05.28 [75 LeetCode] 40 - House Robber (0) 2023.05.28 [75 LeetCode] 38 - Word Break (3) 2023.05.28 [75 LeetCode] 37 - Reverse Bits (0) 2023.05.25 [75 LeetCode] 36 - Search in Rotated Sorted Array (0) 2023.05.25