Description Link to heading

494.target-sum

Solution Link to heading

Actually, what we need to do is choose some numbers whose sum is $\max((sum + target) / 2, (sum - target) / 2)$ in this array. So we can change this problem to a 01-knapsack-problem, and dynamic programming can be used to solve this problem. Also, backtracking can be used to solve this problem.

In this problem, dp[i][j] should denotes the number of methods to make the sum of number selected to be j when considering the first i numbers.

Code Link to heading 

#include <vector>
using std::vector;
class Solution {
  private:
    int max(int a, int b) {
        return a > b ? a : b;
    }

  public:
    int findTargetSumWays(vector<int> &nums, int target) {
        int sum = 0;
        vector<int> my_num(nums.size() + 1, 0);
        for (int i = 0; i < nums.size(); i++) {
            sum += nums[i];
            my_num[i + 1] = nums[i];
        }
        if ((sum + target) % 2 == 1)
            return 0;
        vector<int> res(1001, 0);
        res[0] = 1;
        target = max((sum + target) / 2, (sum - target) / 2);
        // int cnt = 0;
        for (int i = 1; i <= nums.size(); i++) {
            for (int j = target; j >= my_num[i]; j--) {
                // if (my_num[i] == 0)
                //     res[j] = res[j] + 1;
                // else
                //     res[j] = max(res[j], res[j - my_num[i]]);
                res[j] = res[j] + res[j - my_num[i]];
            }
        }
        return res[target];
    }
};