algoadvance

Leetcode 377. Combination Sum IV

Problem Statement

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

The problem differs from the combination sum problem because the order of the integers in the combination matters.

Example 1:

Example 2:

Clarifying Questions

  1. Q: Can we use negative numbers in the nums array?
    • A: No, all the numbers in nums are positive and distinct.
  2. Q: Can nums be empty or target be zero?
    • A: No, the problem guarantees there will always be at least one number in nums and target will be a positive integer.

Strategy

We will use Dynamic Programming (DP) to solve this problem. The idea is to build an array dp where dp[i] represents the number of combinations that add up to the target i.

Steps:

  1. Initialization:
    • Initialize the DP array of size target + 1 with zeros: std::vector<int> dp(target + 1, 0).
    • Set dp[0] = 1 because there’s one way to reach the target 0, which is by using no elements.
  2. DP Update:
    • Iterate through each target value from 1 to target.
    • For each target value, iterate through each number in nums.
    • If the number is less than or equal to the current target, update the DP array by adding the value of dp[current target - num].
  3. Result:
    • The final result will be dp[target] which will give us the number of combinations to form the target.

Time Complexity

Code

#include <iostream>
#include <vector>

int combinationSum4(std::vector<int>& nums, int target) {
    std::vector<int> dp(target + 1, 0);
    dp[0] = 1; // There is one way to reach target 0, by using no elements.

    for (int i = 1; i <= target; ++i) {
        for (const int& num : nums) {
            if (i - num >= 0) {
                dp[i] += dp[i - num];
            }
        }
    }

    return dp[target];
}

int main() {
    std::vector<int> nums1 = {1, 2, 3};
    int target1 = 4;
    std::cout << "Number of combinations for target " << target1 << " is: " << combinationSum4(nums1, target1) << std::endl; // Output: 7

    std::vector<int> nums2 = {9};
    int target2 = 3;
    std::cout << "Number of combinations for target " << target2 << " is: " << combinationSum4(nums2, target2) << std::endl; // Output: 0

    return 0;
}

The provided code snippet initializes the DP array, updates it based on possible sums for each target value, and finally prints the result for provided cases.

Cut your prep time in half and DOMINATE your interview with AlgoAdvance AI