<p>Given an array of <strong>distinct</strong> integers <code>nums</code> and a target integer <code>target</code>, return <em>the number of possible combinations that add up to</em>&nbsp;<code>target</code>.</p>

<p>The test cases are generated so that the answer can fit in a <strong>32-bit</strong> integer.</p>

<p>&nbsp;</p>
<p><strong class="example">Example 1:</strong></p>

<pre>
<strong>Input:</strong> nums = [1,2,3], target = 4
<strong>Output:</strong> 7
<strong>Explanation:</strong>
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.
</pre>

<p><strong class="example">Example 2:</strong></p>

<pre>
<strong>Input:</strong> nums = [9], target = 3
<strong>Output:</strong> 0
</pre>

<p>&nbsp;</p>
<p><strong>Constraints:</strong></p>

<ul>
	<li><code>1 &lt;= nums.length &lt;= 200</code></li>
	<li><code>1 &lt;= nums[i] &lt;= 1000</code></li>
	<li>All the elements of <code>nums</code> are <strong>unique</strong>.</li>
	<li><code>1 &lt;= target &lt;= 1000</code></li>
</ul>

<p>&nbsp;</p>
<p><strong>Follow up:</strong> What if negative numbers are allowed in the given array? How does it change the problem? What limitation we need to add to the question to allow negative numbers?</p>

#include <vector>
using namespace std;

class Solution {
public:
    vector<int> nums; // Store the input numbers
    vector<int> memo; // Memoization table

    // Wrapper function to call the recursive function
    int combinationSum4(vector<int>& nums, int target) {
        this->nums = nums;
        // Initialize memoization table with -1 for all values
        memo = vector<int>(target + 1, -1);
        // Start the recursive count from the target amount
        return count_ways_sum(target);
    }

    // Recursive function to count the number of ways to sum to 'target'
    int count_ways_sum(int target) {
        // Base case: if target is less than 0, it's not a valid combination
        if (target < 0) {
            return 0;
        }

        // Base case: if target is exactly 0, we found a valid combination
        if (target == 0) {
            return 1;
        }

        // Check the memoization table to avoid recomputation
        auto& ret = memo[target];
        if (ret != -1) {
            return ret;
        }

        // Initialize ret to 0 before calculating the result
        ret = 0;

        // Try all possible numbers (no index needed, we're looking for permutations)
        // Loop through each number in `nums` to explore how it can be used to reduce the target.
        for (auto& val : nums) {
            // Recursive step: reduce target by `val` and calculate the number of ways
            // to reach the new target.
            // This line works like a loop because we are trying all permutations by reducing the 
            // target with the current `val` and then calling the function recursively to see 
            // how many ways we can form the reduced target.
            // 
            // Example:
            // If nums = [1, 2, 3] and target = 4, and we are currently trying to use the number 2:
            // - The recursive call `count_ways_sum(target - 2)` is `count_ways_sum(2)`.
            // - This will check how many ways we can form the target 2 using the numbers [1, 2, 3].
            // - Similarly, the function will be called for each `val` in `nums`, accumulating the number
            //   of valid ways to form the target 4 by summing the results of each recursive call.
            ret += count_ways_sum(target - val);
        }

        // Return the result stored in memo[target]
        return ret;
    }
};

/*
Time Complexity:
----------------
The time complexity is O(n * target), where:
- `n` is the number of elements in the input vector `nums`.
- `target` is the given target value.

This is because we solve every subproblem `count_ways_sum(target)` exactly once, and there are at most `target + 1` subproblems. 
For each subproblem, we iterate over the `nums` array, which has `n` elements. Thus, each subproblem takes O(n) time.

Space Complexity:
-----------------
The space complexity is O(target), where:
- We use a memoization table (`memo`) of size `target + 1` to store results for subproblems.
- The recursion depth is proportional to the value of `target`, so the call stack depth is also O(target).
*/

8400