Here, We see Combination Sum IV LeetCode Solution. This Leetcode problem is done in many programming languages like C++, Java, JavaScript, Python, etc. with different approaches.
List of all LeetCode Solution
Combination Sum IV LeetCode Solution
Table of Contents
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
Combination Sum IV LeetCode Solution 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];
}
};
Code language: PHP (php)
Combination Sum IV LeetCode Solution 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];
}
}
Code language: PHP (php)
Combination Sum IV Solution 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];
};
Code language: JavaScript (javascript)
Combination Sum IV Solution 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]