Combination Sum IV Solutions in C++

// 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 elements
        for(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] to
                    sol[i] += sol[i - nums[j]];
            }
        }
        return sol[target];
    }
};

/// 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;
}

/// 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;
}