Today I have done leetcode's December LeetCoding Challenge with cpp.

December LeetCoding Challenge 26

Description

Target Sum

You are given an integer array nums and an integer target.

You want to build an expression out of nums by adding one of the symbols '+' and '-' before each integer in nums and then concatenate all the integers.

• For example, if nums = [2, 1], you can add a '+' before 2 and a '-' before 1 and concatenate them to build the expression "+2-1".

Return the number of different expressions that you can build, which evaluates to target.

Example 1:

Input: nums = [1,1,1,1,1], target = 3
Output: 5
Explanation: There are 5 ways to assign symbols to make the sum of nums be target 3.
-1 + 1 + 1 + 1 + 1 = 3
+1 - 1 + 1 + 1 + 1 = 3
+1 + 1 - 1 + 1 + 1 = 3
+1 + 1 + 1 - 1 + 1 = 3
+1 + 1 + 1 + 1 - 1 = 3

Example 2:

Input: nums = [1], target = 1
Output: 1

Constraints:

• 1 <= nums.length <= 20
• 0 <= nums[i] <= 1000
• 0 <= sum(nums[i]) <= 1000
• -1000 <= target <= 1000

Solution

simple dfs

class Solution {
  int answer = 0;
  void dfs(vector<int> &nums, int pos, int target) {
    if(pos == nums.size()) {
      answer += !target;
      return;
    }
    dfs(nums, pos + 1, target - nums[pos]);
    dfs(nums, pos + 1, target + nums[pos]);
  }
public:
  int findTargetSumWays(vector<int>& nums, int target) {
    dfs(nums, 0, target);
    return answer;
  }
};

// Accepted
// 140/140 cases passed (807 ms)
// Your runtime beats 18.96 % of cpp submissions
// Your memory usage beats 68.89 % of cpp submissions (11.6 MB)

then I think it should be feasible for memoriezed computation

class Solution {
  int answer = 0;
  void dfs(vector<int> &nums, vector<map<int, int>> &dp, int pos) {
    if(pos == nums.size()) {
      dp[pos][0] = 1;
      return;
    }
    dfs(nums, dp, pos + 1);
    for(auto [result, count] : dp[pos + 1]) {
      dp[pos][result + nums[pos]] += count;
      dp[pos][result - nums[pos]] += count;
    }
  }
public:
  int findTargetSumWays(vector<int>& nums, int target) {
    vector<map<int, int>> dp(nums.size() + 1);
    dfs(nums, dp, 0);
    return dp[0][target];
  }
};

// Accepted
// 140/140 cases passed (143 ms)
// Your runtime beats 45.95 % of cpp submissions
// Your memory usage beats 18.17 % of cpp submissions (52.8 MB)

I finally checked the constraints and realized I could do more optimization

class Solution {
  int answer = 0;
  void dfs(vector<int> &nums, int dp[][2001], int pos) {
    if(pos == nums.size()) {
      return;
    }
    dfs(nums, dp, pos + 1);
    for(int i = 0; i < 2001; ++i) {
      if(!dp[pos + 1][i]) continue;
      dp[pos][i + nums[pos]] += dp[pos + 1][i];
      dp[pos][i - nums[pos]] += dp[pos + 1][i];
    }
  }
public:
  int findTargetSumWays(vector<int>& nums, int target) {
    int dp[21][2001] = {};
    dp[nums.size()][1000] = 1;
    dfs(nums, dp, 0);
    return dp[0][target + 1000];
  }
};

// Accepted
// 140/140 cases passed (5 ms)
// Your runtime beats 76.1 % of cpp submissions
// Your memory usage beats 64.14 % of cpp submissions (11.9 MB)