# Combination Sum IV Solutions in C++

Number 377

Difficulty Medium

Acceptance 45.3%

Link LeetCode

Other languages —

## Solutions

### C++ solution by haoel/leetcode

// Source : https://leetcode.com/problems/combination-sum-iv/// Author : Calinescu Valentin// Date : 2016-08-07/* Solution* --------* 1) Dynamic Programming - O(N * target)** We notice that any sum S can be written as S_prev + nums[i], where S_prev is a sum of* elements from nums and nums[i] is one element of the array. S_prev is always smaller* than S so we can create the array sol, where sol[i] is the number of ways one can* arrange the elements of the array to obtain sum i, and populate it from 1 to target,* as the solution for i is made up of previously computed ones for numbers smaller than* i. The final answer is sol[target], which is returned at the end.** Follow up:** If the array contains negative numbers as well as positive ones we can run into a cycle* where some subset of the elements have sum 0 so they can always be added to an existing* sum, leading to an infinite number of solutions. The limitation that we need is a rule* to be followed by the input data, that which doesn't allow this type of subsets to exist.*/class Solution {public:int combinationSum4(vector<int>& nums, int target) {int sol[target + 1];sol[0] = 1;//starting point, only 1 way to obtain 0, that is to have 0 elementsfor(int i = 1; i <= target; i++){sol[i] = 0;for(int j = 0; j < nums.size(); j++){if(i >= nums[j])//if there is a previously calculated sum to add nums[j] tosol[i] += sol[i - nums[j]];}}return sol[target];}};

### C++ solution by liuyubobobo/Play-Leetcode

/// Source : https://leetcode.com/problems/combination-sum-iv/description//// Author : liuyubobobo/// Time : 2018-03-04#include <iostream>#include <vector>using namespace std;/// Memory Search/// Time Complexity: O(n * target)/// Space Complexity: O(n * target)class Solution {private:vector<int> memo;public:int combinationSum4(vector<int>& nums, int target) {if(nums.size() == 0)return 0;memo = vector<int>(target + 1, -1);solve(nums, target);return memo[target];}private:int solve(const vector<int>& nums, int target){if(target == 0)return 1;if(memo[target] != -1)return memo[target];int res = 0;for(int i = 0; i < nums.size() ; i ++)if(target >= nums[i])res += solve(nums, target - nums[i]);return memo[target] = res;}};int main() {vector<int> nums1 = {1, 2, 3};int target1 = 4;cout << Solution().combinationSum4(nums1, target1) << endl;return 0;}

### C++ solution by liuyubobobo/Play-Leetcode

/// Source : https://leetcode.com/problems/combination-sum-iv/description//// Author : liuyubobobo/// Time : 2018-02-28/// updated: 2019-03-31#include <iostream>#include <vector>using namespace std;/// Dynamic Programming/// Time Complexity: O(n * target)/// Space Complexity: O(target)class Solution {public:int combinationSum4(vector<int>& nums, int target) {int n = nums.size();if(n == 0)return 0;vector<int> memo(target + 1, 0);memo[0] = 1;for(int i = 1; i <= target; i++)for(int j = 0; j < n; j ++)if(nums[j] <= i){if(memo[i] == -1 || memo[i - nums[j]] == -1 ||(long long)memo[i] + (long long)memo[i - nums[j]] > INT_MAX)memo[i] = -1;else memo[i] += memo[i - nums[j]];}assert(memo[target] != -1);return memo[target];}};int main() {vector<int> nums1 = {1, 2, 3};int target1 = 4;cout << Solution().combinationSum4(nums1, target1) << endl;return 0;}