LeetCode #494 Target Sum

Medium

Problem

You are given a list of non-negative integers, a1, a2, …, an, and a target, S. Now you have 2 symbols + and -. For each integer, you should choose one from + and - as its new symbol.

Find out how many ways to assign symbols to make sum of integers equal to target S.

Example 1:

Input: nums is [1, 1, 1, 1, 1], S is 3. 
Output: 5
Explanation: 
-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
There are 5 ways to assign symbols to make the sum of nums be target 3.

Note:

1. The length of the given array is positive and will not exceed 20.
2. The sum of elements in the given array will not exceed 1000.
3. Your output answer is guaranteed to be fitted in a 32-bit integer.

Solution — Recursion

If we use recursion only, it will reach time limit of LeetCode. Hence, we’d like to use memoization on possible branch so it will not be calculated again. It’s noted that because sum of nums are given to 1000, we can use a memo matrix with size 2001 for saving all possible results. If the limit is not given, we could only use naive recursive approach.

Complexity

Because we have a memo matrix for saving calculated result. It only needs up to size of memo time for filling this matrix. Therefore, its time complexity is O(nm) if n denotes to size of nums list and m denotes to the range of sum. In this problem, range of sum is given in -1000 ~ 1000, so it’s time complexity will be O(n) actually.

For space complexity, because the memo matrix takes O(n) space and the depth of recursion tree is O(n). Therefore, it takes O(n+n) = O(n) extra space.

Solution — Dynamic Programming

Because we have already known the range of sum, we can increasingly update the record matrix until all element in nums are iterated by this formula:

next[sums + current] = next[sums + current] + record[sums]

next[sums -current] = next[sums -current] + record[sums]

Complexity

Obviously, it iterates entire nums list and run through the range of sum in each iteration. Therefore, the time complexity is O(nm) if n denotes to size of nums and m denotes to the range of sum. And time complexity will become O(n) because we have already known the range will between -1000 and 1000.

For space complexity, the we only maintain a dp list which uses O(n) extra space.