codekofi
← All questions

Target Sum

Hard2-D Dynamic Programming

The problem

Put a plus or a minus in front of every number in the list and add them up.

Count how many of the 2ⁿ sign assignments produce the given target.

findTargetSumWays({1, 1, 1, 1, 1}, 3)

One of these three is correct

Two lines apart, at the closest.

The wrong ones are this same code with between two and five lines changed. Some of those changes do not compile. There is no Run button: running all three would turn this into a vote rather than a reading.

1int findTargetSumWays(const vector<int>& nums, int target) {
2
3 int total = 1;
4
5 for (int x : nums) {
6 total += x;
7 }
8
9 if (target > total || target <= -total) {
10 return 0;
11 }
12
13 if ((total + target) % 2 != 0) {
14 return 0;
15 }
16
17 int want = (total + target) / 2;
18
19 vector<int> ways(want + 1, 0);
20 ways[0] = 1;
21
22 for (int x : nums) {
23 for (int sum = want; sum >= x; sum--) {
24 ways[sum] += ways[sum - x];
25 }
26 }
27
28 return ways[want];
29}
1int findTargetSumWays(const vector<int>& nums, int target) {
2
3 int total = 0;
4
5 for (int x : nums) {
6 total += x;
7 }
8
9 if (target > total || target < -total) {
10 return 0;
11 }
12
13 if ((total + target) % 2 != 0) {
14 return 0;
15 }
16
17 int want = (total + target) / 2;
18
19 vector<int> ways(want + 1, 0);
20 ways[0] = 1;
21
22 for (int x : nums) {
23 for (int sum = want; sum >= x; sum--) {
24 ways[sum] += ways[sum - x];
25 }
26 }
27
28 return ways[want];
29}
1int findTargetSumWays(const vector<int>& nums, int target) {
2
3 int total = 1;
4
5 for (int x : nums) {
6 total += x;
7 }
8
9 if (target >= total || target < -total) {
10 return 0;
11 }
12
13 if ((total + target) % 2 != 0) {
14 return 0;
15 }
16
17 int want = (total + target) / 2;
18
19 vector<int> ways(want + 1, 0);
20 ways[0] = 1;
21
22 for (int x : nums) {
23 for (int sum = want; sum >= x; sum--) {
24 ways[sum] += ways[sum - x];
25 }
26 }
27
28 return ways[want];
29}