문제 개요
모든 요소가 양수이면서 중복이 없는 정수 배열이 주어졌을 때, 배열의 숫자들을 더하여 목표값(target)이 되는 조합의 수를 구하는 문제입니다. 이때 순서가 다른 조합은 서로 다른 조합으로 간주한다는 점에 유의해야 합니다.
예를 들어 배열이 [1, 2, 3]이고 목표값이 4라면, 가능한 조합은 [[1,1,1,1], [1,1,2], [1,2,1], [2,1,1], [1,3], [3,1], [2,2]]로 총 7가지입니다. 따라서 출력 결과는 7이 됩니다.
해결 접근 방법
이 문제는 메모이제이션(Memoization)을 적용한 재귀 함수를 사용하면 효율적으로 해결할 수 있습니다. solve()라는 재귀 함수에 배열(nums), 목표값(target), 그리고 동적 프로그래밍(DP)을 위한 dp 배열을 전달하며 다음 과정을 수행합니다.
- target이 0이면 1을 반환합니다. (조합 하나를 완성했다는 의미)
- dp[target]이 -1이 아니라면 이미 계산된 값이 있으므로 dp[target]을 그대로 반환합니다.
- ans를 0으로 초기화합니다.
- i를 0부터 nums 배열의 끝까지 반복합니다.
- target >= nums[i]인 경우, ans에 solve(nums, target − nums[i], dp)의 반환값을 더합니다.
- dp[target]에 ans를 저장합니다.
- ans를 반환합니다.
C++ 구현 예제
다음 구현 예제를 통해 더 자세히 이해해 보겠습니다.
#include <bits/stdc++.h>
using namespace std;
class Solution {
public:
int combinationSum4(vector<int>& nums, int target) {
vector <int> dp(target + 1, -1);
return helper(nums, target, dp);
}
int helper(vector <int>& nums, int target, vector <int>& dp){
if(target == 0)return 1;
if(dp[target] != -1)return dp[target];
int ans = 0;
for(int i = 0; i < nums.size(); i++){
if(target >= nums[i]){
ans += helper(nums, target - nums[i], dp);
}
}
return dp[target] = ans;
}
};
main(){
Solution ob;
vector<int> v = {1,2,3};
cout << ob.combinationSum4(v, 4);
}
입력
[1,2,3] 4
출력
7
복잡도 분석
이 알고리즘의 시간 복잡도는 O(target × n)입니다. 여기서 target은 목표값, n은 배열의 길이를 의미합니다. 각 목표값에 대한 결과를 dp 배열에 한 번만 계산하여 저장하기 때문에, 동일한 하위 문제를 반복해서 풀지 않아 일반적인 완전 탐색보다 훨씬 효율적입니다. 공간 복잡도는 dp 배열 저장을 위해 O(target)이 필요합니다.