Target Sum

Problem Statement

Given an integer array nums and an integer target, return the number of ways to assign + or - to each element such that the sum equals target. Assume all values in nums are non-negative integers; the + or - is the sign you assign to each element, not the element's original sign.

Input Format

Line 1: Space-separated integers representing nums. Line 2: Target integer.

Output Format

Number of ways to achieve the target sum.

Examples

Example 1:

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

Ways: -1+1+1+1+1, +1-1+1+1+1, +1+1-1+1+1, +1+1+1-1+1, +1+1+1+1-1