[LeetCode] Target Sum

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:

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.

Constraints:

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

Approach: Let's start with brute force approach. We can use recursion to solve this problem. Basically at every index we have two choices; either we can add it to the sum or we can subtract it from the sum. With this intuition, we can solve this problem as follows:

• // initially currIndex, count and currSum will be 0.
• Calculate(int[] nums, int currIndex, int currSum, int S, ref int count) 
• IF currIndex == Length(sum)
• IF currSum == S
• count = count + 1
• Calculate(nums, currIndex + 1, currSum + nums[currIndex], S, ref count)
• Calculate(nums, currIndex + 1, currSum - nums[currIndex], S, ref count)

count will be our answer. This will solve our problem but it is an expensive solution and will take exponential time (2 ^ n). Let's now move to our optimized solution.

I think looking at the brute force approach, you would have realized that we can actually use DP here as we are solving same sub problems multiple times. We can maintain a 2D table where table[i][j] will tell the number of ways to achieve sum = j with subarray nums[0...i]. Obviously table[n - 1][S] will be our answer. We can fill the table as follows:

• table[0][nums[0]] = 1
• table[0][-nums[0]] += 1 // nums[0] = 0 in that case we need to add
• FOR i = 1 to n
• FOR j = 0 to 1000
• IF table[i - 1][j] > 0
• table[i][j + nums[i]] += table[i - 1][j]
• table[i][j - nums[i]] += table[i - 1][j]

You can observe that there is one problem here as j - nums[i] or -nums[0] can be negative. To resolve this problem we can use the fact that 0 <= S <= 1000. We can always use +1000 for sum and with this our inner loop will become:

• FOR j = -1000 to 1000
• IF table[i - 1][j + 1000] > 0
• table[i][j + nums[i] + 1000] += table[i - 1][j + 1000]
• table[i][j - nums[i] + 1000] += table[i - 1][j + 1000]

Obviously our initialization will be changed too:

• table[0][nums[0] + 1000] = 1
• table[0][-nums[0] + 1000] += 1

That's all!

Implementation in C#:

        public int FindTargetSumWays(int[] nums, int sum)

        {

            int[,] table = new int[nums.Length, 2001];

            table[0, nums[0] + 1000] = 1;

            table[0, -nums[0] + 1000] += 1;

            for (int i = 1; i < nums.Length; ++i)

            {

                for (int j = -1000; j <= 1000; ++j)

                {

                    if (table[i - 1, j + 1000] > 0)

                    {

                        table[i, j + nums[i] + 1000] += table[i - 1, j + 1000];

                        table[i, j - nums[i] + 1000] += table[i - 1, j + 1000];

                    }

                }

            }

            return sum > 1000 ? 0 : table[nums.Length - 1, sum + 1000]; 

        }

Complexity: O(n * S)