Combination Sum IV - Medium - L
Published:
Question
- https://leetcode.com/problems/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.
Approach
- DP
Solution
class Solution {
public:
int combinationSum4(vector<int>& nums, int target) {
vector<int>dp(target+1,-1);
return solve(nums,target,dp);
}
int solve(vector<int>& nums,int target,vector<int>& dp)
{
if(target==0)
return 1;
if(dp[target]!=-1)
return dp[target];
int res=0;
for(int i=0;i<nums.size();i++)
{
if(target>=nums[i])
res+=solve(nums,target-nums[i],dp);
}
dp[target]=res;
return res;
}
};