Table of Contents

# Target Sum – LeetCode Solution Java , Python 3, Python 2 , C , C++, Best and Optimal Solutions , All you need.

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 = 3Output:5Explanation: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 = 1Output:1

**Constraints:**

`1 <= nums.length <= 20`

`0 <= nums[i] <= 1000`

`0 <= sum(nums[i]) <= 1000`

`-1000 <= target <= 1000`

# C++ Target Sum LeetCode Solution

```
``````
class Solution {
public:
int findTargetSumWays(vector<int>& nums, int s) {
int sum = accumulate(nums.begin(), nums.end(), 0);
return sum < s || (s + sum) & 1 ? 0 : subsetSum(nums, (s + sum) >> 1);
}
int subsetSum(vector<int>& nums, int s) {
int dp[s + 1] = { 0 };
dp[0] = 1;
for (int n : nums)
for (int i = s; i >= n; i--)
dp[i] += dp[i - n];
return dp[s];
}
};
```

# Java Target Sum LeetCode Solution

```
``````
public int findTargetSumWays(int[] nums, int s) {
int sum = 0;
for (int n : nums)
sum += n;
return sum < s || (s + sum) % 2 > 0 ? 0 : subsetSum(nums, (s + sum) >>> 1);
}
public int subsetSum(int[] nums, int s) {
int[] dp = new int[s + 1];
dp[0] = 1;
for (int n : nums)
for (int i = s; i >= n; i--)
dp[i] += dp[i - n];
return dp[s];
}
```

# Python 3 Target Sum LeetCode Solution

```
``````
def findTargetSumWays(self, A, S):
count = collections.Counter({0: 1})
for x in A:
step = collections.Counter()
for y in count:
step[y + x] += count[y]
step[y - x] += count[y]
count = step
return count[S]
```

Array-1180

String-562

Hash Table-412

Dynamic Programming-390

Math-368

Sorting-264

Greedy-257

Depth-First Search-256

Database-215

Breadth-First Search-200

Tree-195

Binary Search-191

Matrix-176

Binary Tree-160

Two Pointers-151

Bit Manipulation-140

Stack-133

Heap (Priority Queue)-117

Design-116

Graph-108

Simulation-103

Prefix Sum-96

Backtracking-92

Counting-86

Sliding Window-73

Linked List-69

Union Find-66

Ordered Set-48

Monotonic Stack-47

Recursion-43

Trie-41

Binary Search Tree-40

Divide and Conquer-40

Enumeration-39

Bitmask-37

Queue-33

Memoization-32

Topological Sort-31

Geometry-30

Segment Tree-27

Game Theory-24

Hash Function-24

Binary Indexed Tree-21

Interactive-18

Data Stream-17

String Matching-17

Rolling Hash-17

Shortest Path-16

Number Theory-16

Combinatorics-15

Randomized-12

Monotonic Queue-9

Iterator-9

Merge Sort-9

Concurrency-9

Doubly-Linked List-8

Brainteaser-8

Probability and Statistics-7

Quickselect-7

Bucket Sort-6

Suffix Array-6

Minimum Spanning Tree-5

Counting Sort-5

Shell-4

Line Sweep-4

Reservoir Sampling-4

Eulerian Circuit-3

Radix Sort-3

Strongly Connected Componen-t2

Rejection Sampling-2

Biconnected Component-1