text: /****************************************************
  Date: April 19th
  
  link: https://leetcode.com/explore/challenge/card/april-leetcoding-challenge-2021/595/week-3-april-15th-april-21st/3709/
  ****************************************************/
  
  #include <iostream>
  #include <vector>
  #include <list>
  #include <algorithm>
  #include <string>
  #include <stack>
  #include <queue>
  #include <map>
  #include <unordered_map>
  #include <unordered_set>
  #include <cmath>
  #include <limits.h>
  
  using namespace std;
  
  /*
    Q: 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 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.
  
    Example 2:
      Input: nums = [9], target = 3
      Output: 0
  
    Constraints:
      1 <= nums.length <= 200
      1 <= nums[i] <= 1000
      All the elements of nums are unique.
      1 <= target <= 1000
  
    Follow up: 
      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?
  */
  class Solution 
  {  
  public:
    int combinationSum4(vector<int>& nums, int target) 
    {
      vector<unsigned int> result(target + 1);
      result[0] = 1;
      for (int i = 1; i <= target; ++i) 
      {
        for (int x : nums) 
        {
          if (i >= x) 
          {
            result[i] += result[i - x];
          }
        }
      }
  
      return result[target];
    }
  };