Last updated on February 2nd, 2025 at 05:15 am

Here, we see the Combination Sum IV LeetCode Solution. This Leetcode problem is solved using different approaches in many programming languages, such as C++, Java, JavaScript, Python, etc.

List of all LeetCode Solution

Topics

Dynamic Programming

Companies

Facebook, Google, Snapchat

Level of Question

Medium

Combination Sum IV LeetCode Solution

1. 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 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

2. Coding Pattern Used in Solution

The provided code uses the Dynamic Programming pattern, specifically a variation of the Unbounded Knapsack problem. The problem involves finding the number of ways to achieve a target sum using an array of numbers, where each number can be used multiple times.

3. Code Implementation in Different Languages

3.1 Combination Sum IV C++

class Solution {
public:
    int combinationSum4(vector<int>& nums, int target) {
        vector<unsigned int> dp(target + 1, 0);
        dp[0] = 1;
        for (int i = 1; i <= target; ++i) {
            for (int num : nums) {
                if (i - num >= 0) {
                    dp[i] += dp[i - num];
                }
            }
        }
        return dp[target];
    }
};

3.2 Combination Sum IV Java

class Solution {
    public int combinationSum4(int[] nums, int target) {
        int[] dp = new int[target + 1];
        dp[0] = 1;
        for (int i = 1; i <= target; i++) {
            for (int num : nums) {
                if (i - num >= 0) {
                    dp[i] += dp[i - num];
                }
            }
        }
        return dp[target];        
    }
}

3.3 Combination Sum IV JavaScript

var combinationSum4 = function(nums, target) {
    const dp = Array(target + 1).fill(0);
    dp[0] = 1;
    for (let i = 1; i <= target; i++) {
        for (const num of nums) {
            if (i - num >= 0) {
                dp[i] += dp[i - num];
            }
        }
    }
    return dp[target];    
};

3.4 Combination Sum IV Python

class Solution(object):
    def combinationSum4(self, nums, target):
        dp = [0] * (target + 1)
        dp[0] = 1
        for i in range(1, target + 1):
            for num in nums:
                if i - num >= 0:
                    dp[i] += dp[i - num]
        return dp[target]

4. Time and Space Complexity

	Time Complexity	Space Complexity
C++	O(M * N)	O(M)
Java	O(M * N)	O(M)
JavaScript	O(M * N)	O(M)
Python	O(M * N)	O(M)