✉️문제
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
📝 접근
전형적인 DP 알고리즘 문제이다. 이전 경우의 수를 더 해나가면 된다.
[1,2,3]이라는 숫자가 있고 target = 4일 때 다음과 같이 1로 만들 수 있는 경우의 수, 1과 2를 만드는 경우의 수로 나눌 수 있지만
// 1이라는 숫자로 만드는 경우의 수
|-------------------|
| 1 | 1 | 1 | 1 | 1 |
|-------------------|
// 1과 2로 만드는 경우의 수
|-------------------|
| 1 | 1 | 2 | 2 | 3 |
|-------------------|코드적으로는 i번 째일 때, 이전 경우의 수와 조합이 생기는지 확인하는 편이 더 간단하다.
🗝 문제풀이
public int combinationSum4(int[] nums, int target) {
int[] dp = new int[target + 1];
dp[0] = 1;
for(int i = 1; i <= target; i++) {
for(int num : nums) {
if(i >= num) {
dp[i] += dp[i - num];
}
}
}
return dp[target];
}