Combination Sum IV Problem


Description

LeetCode Problem 377.

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

The answer is guaranteed to fit in a 32-bit integer.

Example 1:

1
2
3
4
5
6
7
8
9
10
11
12
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:

1
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


Sample C++ Code

We declare a dp variable as an array of long with length target + 1 since we will use up to the index target of it.

We set the very first cell to 1 and then loop with i from 1 to target (incuded) and:

  • Set dp[i] to 0 (no need to go for an expensive isolated initialisation loop otherwise);
  • Loop through all the elements n in nums and:

    • if i >= n add dp[i - n] to dp[i] (meaning we can reach that place from adding n to all the dp[i - n] solutions we computed before);
    • if dp[i] overflows the limits of a 32bit, we can just break, since that is not a viable solution.

Once done, we can just return dp[target].

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
class Solution {
public:
    int combinationSum4(vector<int>& nums, int target) {
        // support variables
        long dp[target + 1];
        dp[0] = 1;
        // populating dp
        for (int i = 1; i <= target; i++) {
            // setting the initial value of a cell to 0
            dp[i] = 0;
            // updating dp[i] with all the previous combinations we can reach from there
            for (int n: nums) {
                if (i >= n) dp[i] += dp[i - n];
                if (dp[i] > INT_MAX) break;
            }
        }
        return dp[target];
    }
};




Related Posts

Count Numbers With Unique Digits Problem

LeetCode 357. Given an integer n, return the count of...

Combination Sum IV Problem

LeetCode 377. Given an array of distinct integers nums and...

Coin Change Problem

LeetCode 322. You are given an integer array coins representing...

Burst Balloons Problem

LeetCode 312. You are given n balloons, indexed from 0...

Best Time To Buy And Sell Stock With Cooldown Problem

LeetCode 309. You are given an array prices where prices[i]...

Maximum Product Subarray Problem

LeetCode 152. Given an integer array nums, find a contiguous...