Problem Statement

Given an array of distinct integers nums and a target integer target, return the number of possible combinations that add up to the target.

The answer is guaranteed to fit in a 32-bit integer.
Example 1:-
Input: nums = [1,2,3], target = 4
Output: 7
Explanation:
The possible combination ways are:
(1, 1, 1, 1)
(1, 1, 2)
(1, 2, 1)
(1, 3)
(2, 1, 1)
(2, 2)
(3, 1)
Note that different sequences are counted as different combinations.

Approach:-

The question is very similar to the famous staircase question.
The only difference is that in the staircase question we are given the no. of possible steps beforehand only and we can use them directly, but in this question, all possible steps or numbers are given in a nums vector. We can here use the nums vector to call for all possible steps as shown in the solution below. Normal recursive implementation, as usual, gives TLE, it can be optimized by adding a temporary array and saving the values in it 0R by using Memoization.

class Solution {
public:
    int combinationSum4(vector<int>& nums, int target, int dp[]) {
        if(target <0) return 0;
        if(target==0) return 1;
        if(dp[target]!=-1) return dp[target];
        int ans=0;
        for(int i=0;i<nums.size();i++)
        {
            ans+=combinationSum4(nums,target-nums[i], dp);
        }
        dp[target]=ans;
        return ans;
    }
    int combinationSum4(vector<int>& nums, int target) {
        int dp[1001];
        for(int i=0;i<1001;i++) dp[i]=-1;    
        return combinationSum4(nums,target,dp);
        }
};