Target Sum

Target Sum is a Medium Data Structures and Algorithms interview problem you can solve, run and submit on Thita.ai. It belongs to the Dynamic Programming (DP) Patterns pattern, in the 1D Array (0/1 Knapsack Subset Sum Style) subpattern.

Problem statement

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

Topics and companies

Topics: Array, Dynamic Programming, Backtracking.

Reported in interviews at Adobe, Amazon, Bloomberg, Facebook, Google, Microsoft.

How to practise Target Sum on Thita.ai

Starter code is provided in C, C#, C++, Go, Java, JavaScript and Python. Your solution runs against 5 test cases for this problem, with the AI coach available for a hint when you are stuck rather than a finished answer. The reference solution runs in O(n * S) time and O(S) space.

Open Target Sum in the code editor, or read the Target Sum editorial for a worked solution with its approach and complexity analysis.

Where Target Sum sits in the DSA pattern sheet

Problems related to Target Sum

Other problems that use the same 1D Array (0/1 Knapsack Subset Sum Style) and Dynamic Programming (DP) Patterns techniques:

Preparing this workspace.