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 = 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

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

Leave a comment below

Related posts:

Combination Sum – LeetCode Solution Combination Sum III – LeetCode Solution Range Sum Query 2D – Immutable – LeetCode Solution Count of Range Sum – LeetCode Solution Split Array Largest Sum – LeetCode Solution Partition Equal Subset Sum – LeetCode Solution