Target Sum Solutions in C++

// Source : https://leetcode.com/problems/target-sum/
// Author : Bhavesh Mandhan
// Date   : 2020-10-21




class Solution {
public:
    int findTargetSumWays(vector<int>& nums, int S) {
        long int i,j,n,tot=0,sum,zero=0;
        n = nums.size();
        for(i=0;i<n;i++){
            tot+=nums[i];
            if(nums[i]==0){
                zero++;
            }
        }
        if((S+tot)%2!=0 || S>tot){
            return 0;
        }
        sum = (S+tot)/2;
        int dp[n+1][sum+1];
        for(i=1;i<=sum;i++){
            dp[0][i]= 0;
        }
        for(i=0;i<=n;i++){
            dp[i][0]= 1;
        }
        for(i=1;i<=n;i++){
            for(j=1;j<=sum;j++){
                if(nums[i-1]==0 || nums[i-1]>j){
                    dp[i][j] = dp[i-1][j];
                }
                else{
                    dp[i][j] = dp[i-1][j] + dp[i-1][j-nums[i-1]];
                }
            }
        }
        return pow(2,zero)*dp[n][sum];
    }
};

/// Source : https://leetcode.com/problems/target-sum/description/
/// Author : liuyubobobo
/// Time   : 2018-09-14

#include <iostream>
#include <vector>

using namespace std;


/// Backtracking
/// Time Complexity: O(2^n)
/// Space Complexity: O(n)
class Solution {
public:
    int findTargetSumWays(vector<int>& nums, int S) {

        return dfs(nums, 0, 0, S);
    }

private:
    int dfs(const vector<int>& nums, int index, int res, int S){

        if(index == nums.size())
            return res == S;

        int ret = 0;
        ret += dfs(nums, index + 1, res - nums[index], S);
        ret += dfs(nums, index + 1, res + nums[index], S);
        return ret;
    }
};


int main() {

    vector<int> nums = {1, 1, 1, 1, 1};
    cout << Solution().findTargetSumWays(nums, 3) << endl;

    return 0;
}

/// Source : https://leetcode.com/problems/target-sum/description/
/// Author : liuyubobobo
/// Time   : 2018-09-14

#include <iostream>
#include <vector>
#include <stack>

using namespace std;


/// Backtracking
/// Using Stack - Non-recursion solution
///
/// Time Complexity: O(2^n)
/// Space Complexity: O(2^n)
class Solution {
public:
    int findTargetSumWays(vector<int>& nums, int S) {

        stack<int> indexStack, sumStack;
        indexStack.push(0);
        sumStack.push(0);
        int res = 0, index, sum;
        while(!indexStack.empty()){
            index = indexStack.top();
            sum = sumStack.top();
            indexStack.pop();
            sumStack.pop();

            if(index + 1 == nums.size())
                res += (sum + nums[index] == S) + (sum - nums[index] == S);
            else{
                indexStack.push(index + 1);
                sumStack.push(sum + nums[index]);
                indexStack.push(index + 1);
                sumStack.push(sum - nums[index]);
            }
        }
        return res;
    }
};


int main() {

    vector<int> nums = {1, 1, 1, 1, 1};
    cout << Solution().findTargetSumWays(nums, 3) << endl;

    return 0;
}

/// Source : https://leetcode.com/problems/target-sum/description/
/// Author : liuyubobobo
/// Time   : 2018-09-14

#include <iostream>
#include <vector>
#include <map>

using namespace std;


/// Memory Search
/// Using TreeSet
///
/// Time Complexity: O(n * maxNum * log(n * maxNum))
/// Space Complexity: O(n * maxNum)
class Solution {
public:
    int findTargetSumWays(vector<int>& nums, int S) {

        map<pair<int, int>, int> dp;
        return dfs(nums, 0, S, dp);
    }

private:
    int dfs(const vector<int>& nums, int index, int S,
            map<pair<int, int>, int>& dp){

        if(index == nums.size())
            return S == 0;

        pair<int, int> p = make_pair(index, S);
        if(dp.count(p))
            return dp[p];

        int ret = 0;
        ret += dfs(nums, index + 1, S - nums[index], dp);
        ret += dfs(nums, index + 1, S + nums[index], dp);
        return dp[p] = ret;
    }
};


int main() {

    vector<int> nums = {1, 1, 1, 1, 1};
    cout << Solution().findTargetSumWays(nums, 3) << endl;

    return 0;
}

/// Source : https://leetcode.com/problems/target-sum/description/
/// Author : liuyubobobo
/// Time   : 2018-09-14

#include <iostream>
#include <vector>
#include <map>

using namespace std;


/// Memory Search
/// Using 2D-Array
///
/// Time Complexity: O(n * maxNum)
/// Space Complexity: O(n * maxNum)
class Solution {
public:
    int findTargetSumWays(vector<int>& nums, int S) {

        vector<vector<int>> dp(nums.size(), vector<int>(2001, -1));
        return dfs(nums, 0, S, dp);
    }

private:
    int dfs(const vector<int>& nums, int index, int S,
            vector<vector<int>>& dp){

        if(index == nums.size())
            return S == 0;

        if(S + 1000 < 0 || S + 1000 >= 2001)
            return 0;

        if(dp[index][S + 1000] != -1)
            return dp[index][S + 1000];

        int ret = 0;
        ret += dfs(nums, index + 1, S - nums[index], dp);
        ret += dfs(nums, index + 1, S + nums[index], dp);
        return dp[index][S + 1000] = ret;
    }
};


int main() {

    vector<int> nums = {1, 1, 1, 1, 1};
    cout << Solution().findTargetSumWays(nums, 3) << endl;

    return 0;
}

/// Source : https://leetcode.com/problems/target-sum/description/
/// Author : liuyubobobo
/// Time   : 2018-09-14

#include <iostream>
#include <vector>
#include <map>

using namespace std;


/// Dynamic Programming
/// Using 2D-Array
///
/// Time Complexity: O(n * maxNum)
/// Space Complexity: O(n * maxNum)
class Solution {
public:
    int findTargetSumWays(vector<int>& nums, int S) {

        vector<vector<int>> dp(nums.size(), vector<int>(2001, 0));
        dp[0][1000 - nums[0]] += 1;
        dp[0][1000 + nums[0]] += 1;
        for(int i = 1; i < nums.size(); i ++)
            for(int j = 0; j < 2001; j ++){
                if(j - nums[i] >= 0 && j - nums[i] < 2001)
                    dp[i][j] += dp[i - 1][j - nums[i]];
                if(j + nums[i] >= 0 && j + nums[i] < 2001)
                    dp[i][j] += dp[i - 1][j + nums[i]];
            }

        if(1000 + S < 0 || 1000 + S >= 2001)
            return 0;
        return dp[nums.size() - 1][1000 + S];
    }
};


int main() {

    vector<int> nums = {1, 1, 1, 1, 1};
    cout << Solution().findTargetSumWays(nums, 3) << endl;

    return 0;
}

/// Source : https://leetcode.com/problems/target-sum/description/
/// Author : liuyubobobo
/// Time   : 2018-09-14

#include <iostream>
#include <vector>
#include <map>

using namespace std;


/// Dynamic Programming
/// Using 1D Array
///
/// Time Complexity: O(n * maxNum)
/// Space Complexity: O(maxNum)
class Solution {
public:
    int findTargetSumWays(vector<int>& nums, int S) {

        vector<int> dp(2001, 0);
        dp[1000 - nums[0]] += 1;
        dp[1000 + nums[0]] += 1;
        for(int i = 1; i < nums.size(); i ++){
            vector<int> a(2001, 0);
            for(int j = 0; j < 2001; j ++){
                if(j - nums[i] >= 0 && j - nums[i] < 2001)
                    a[j] += dp[j - nums[i]];
                if(j + nums[i] >= 0 && j + nums[i] < 2001)
                    a[j] += dp[j + nums[i]];
            }
            dp = a;
        }

        if(1000 + S < 0 || 1000 + S >= 2001)
            return 0;
        return dp[1000 + S];
    }
};


int main() {

    vector<int> nums = {1, 1, 1, 1, 1};
    cout << Solution().findTargetSumWays(nums, 3) << endl;

    return 0;
}