1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
/**
 * Find the number of different expressions that evaluate to target.
 * Recursion with Memoization approach.
 *
 * @param {number[]} nums - Array of integers
 * @param {number} target - Target sum
 * @return {number} - Number of different expressions
 */
function findTargetSumWays(nums, target) {
  const memo = new Map();
 
  /**
   * Helper function to calculate the number of ways to achieve the target sum.
   *
   * @param {number} index - Current index in the array
   * @param {number} sum - Current sum
   * @return {number} - Number of ways to achieve the target sum
   */
  function calculate(index, sum) {
    // Base case: reached the end of the array
    if (index === nums.length) {
      return sum === target ? 1 : 0;
    }
 
    // Check if we've already computed this subproblem
    const key = `${index},${sum}`;
    if (memo.has(key)) {
      return memo.get(key);
    }
 
    // Add the current number
    const add = calculate(index + 1, sum + nums[index]);
 
    // Subtract the current number
    const subtract = calculate(index + 1, sum - nums[index]);
 
    // Memoize and return
    const result = add + subtract;
    memo.set(key, result);
    return result;
  }
 
  return calculate(0, 0);
}
 
/**
 * Find the number of different expressions that evaluate to target.
 * Dynamic Programming (0/1 Knapsack) approach.
 *
 * @param {number[]} nums - Array of integers
 * @param {number} target - Target sum
 * @return {number} - Number of different expressions
 */
function findTargetSumWaysDP(nums, target) {
  // Calculate the sum of all elements
  const sum = nums.reduce((acc, num) => acc + num, 0);
 
  // Check if it's possible to achieve the target sum
  if ((sum + target) % 2 !== 0 || Math.abs(target) > sum) {
    return 0;
  }
 
  const P = (sum + target) / 2;
 
  // Initialize DP array
  const dp = new Array(P + 1).fill(0);
  dp[0] = 1;
 
  for (const num of nums) {
    for (let j = P; j >= num; j--) {
      dp[j] += dp[j - num];
    }
  }
 
  return dp[P];
}
 
/**
 * Find the number of different expressions that evaluate to target.
 * 2D Dynamic Programming approach.
 *
 * @param {number[]} nums - Array of integers
 * @param {number} target - Target sum
 * @return {number} - Number of different expressions
 */
function findTargetSumWays2D(nums, target) {
  const n = nums.length;
 
  // Calculate the sum of all elements
  const sum = nums.reduce((acc, num) => acc + num, 0);
 
  // Check if it's possible to achieve the target sum
  if (Math.abs(target) > sum) {
    return 0;
  }
 
  // Initialize 2D DP array
  const dp = Array(n + 1).fill().map(() => Array(2 * sum + 1).fill(0));
  dp[0][sum] = 1;  // There's one way to achieve a sum of 0 using 0 elements
 
  for (let i = 1; i <= n; i++) {
    for (let j = 0; j <= 2 * sum; j++) {
      // Add the current number
      if (j - nums[i - 1] >= 0) {
        dp[i][j] += dp[i - 1][j - nums[i - 1]];
      }
 
      // Subtract the current number
      if (j + nums[i - 1] <= 2 * sum) {
        dp[i][j] += dp[i - 1][j + nums[i - 1]];
      }
    }
  }
 
  return dp[n][sum + target];
}
 
// Test cases
console.log(findTargetSumWays([1, 1, 1, 1, 1], 3));  // 5
console.log(findTargetSumWays([1], 1));  // 1
 
console.log(findTargetSumWaysDP([1, 1, 1, 1, 1], 3));  // 5
console.log(findTargetSumWaysDP([1], 1));  // 1
 
console.log(findTargetSumWays2D([1, 1, 1, 1, 1], 3));  // 5
console.log(findTargetSumWays2D([1], 1));  // 1