Combination Sum IV

---

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 test cases are generated so that the answer can 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

---

Try this Problem on your own or check similar problems:

1. Combination Sum

Solution:

Java

public int combinationSum4(int[] nums, int target) {
    Map<Integer, Integer> map = new HashMap<>();
    map.put(0, 1);

    for(int i = 1; i <= target; ++i){
        for(int num: nums){
            if(num <= i){
                map.put(i, map.getOrDefault(i, 0) + map.getOrDefault(i - num, 0));
            }
        }
    }
    return map.getOrDefault(target, 0);
}

JavaScript

/**
 * @param {number[]} nums
 * @param {number} target
 * @return {number}
 */
var combinationSum4 = function (nums, target) {
  let map = new Map();
  map.set(0, 1);

  for (let i = 1; i <= target; ++i) {
    for (let num of nums) {
      if (num <= i) {
        map.set(i, (map.get(i) || 0) + (map.get(i - num) || 0));
      }
    }
  }

  return map.get(target) || 0;
};

Python

class Solution:
    def combinationSum4(self, nums: List[int], target: int) -> int:
        map = {0: 1}

        for i in range(1, target + 1):
            for num in nums:
                if num <= i:
                    map[i] = map.get(i, 0) + map.get(i - num, 0)

        return map.get(target, 0)

C++

class Solution {
public:
    int combinationSum4(vector<int>& nums, int target) {
        vector< unsigned int> map(target+1);
        map[0]=1;

        for(int i=1; i<target+1; i++)
            for(int j=0; j<nums.size(); j++)
                if(nums[j]<=i)
                    map[i] += map[i-nums[j]];

        return map[target];
    }
};

---

Time/Space Complexity:

• Time Complexity: O(n*S) where S is the target, and n is the length of the input array
• Space Complexity: O(S)

---

Explanation:

The implementation of the algorithm is not hard, but understanding the underlying principles might be, so let's break them down:

• We have map instead dp array, but nothing really stops us to use dp array to (since all elements are positive as per problem statement).
• The bulk of the algorithm are two loops and updating the map, map is updated in such way that we always add all possible ways to get to i (where i <= target).
• Actually, the most important part of the algo is the order of the loops. Note that we're first iterating over target, and then for each target we iterate over all values in the input array. This allows us to achieve first of all multiple combinations that add up to target, with same elements but different order (e.g. 1,2,1 and 2,1,1). Second notice that we can reuse the same element to make up each of the targets (e.g. for target i=1 let's say we use element 1, nothing stops us to use that same element for i=2, next iteration of the outer loop).