leetcode
  • LeetCode Problems
  • Array
    • Array Partition I
    • Toeplitz Matrix
    • Find All Numbers Disappeared in an Array
    • Max Area of Island
    • Move Zeros
    • Two Sum II - Input array is sorted
    • Degree of an Array
    • Image Smoother
    • Positions of Large Groups
    • Missing Number
    • Maximum Product of Three Numbers
    • Min Cost Climbing Stairs
    • Longest Continuous Increasing Subsequence
    • Remove Element
    • Pascal's Triangle
    • Maximum Subarray
    • Largest Number At Least Twice of Others
    • Search Insert Position
    • Plus One
    • Find Pivot Index
    • Pascal's Triangle II
    • Two Sum
    • Maximize Distance to Closest Person
    • Maximum Average Subarray I
    • Remove Duplicates from Sorted Array
    • Magic Squares In Grid
    • Contains Duplicate II
    • Merge Sorted Array
    • Can Place Flowers
    • Shortest Unsorted Continuous Subarray
    • K-diff Pairs in an Array
    • Third Maximum Number
    • Rotate Array
    • Non-decreasing Array
    • Find All Duplicates in an Array
    • Teemo Attacking
    • Beautiful Arrangement II
    • Product of Array Except Self
    • Max Chunks To Make Sorted
    • Subsets
    • Best Time to Buy and Sell Stock with Transaction Fee
    • Combination Sum III
    • Find the Duplicate Number
    • Unique Paths
    • Rotate Image
    • My Calendar I
    • Spiral Matrix II
    • Combination Sum
    • Task Scheduler
    • Valid Triangle Number
    • Minimum Path Sum
    • Number of Subarrays with Bounded Maximum
    • Insert Delete GetRandom O(1)
    • Find Minimum in Rotated Sorted Array
    • Sort Colors
    • Find Peak Element
    • Subarray Sum Equals K
    • Subsets II
    • Maximum Swap
    • Remove Duplicates from Sorted Array II
    • Maximum Length of Repeated Subarray
    • Image Overlap
    • Length of Longest Fibonacci Subsequence
  • Contest
    • Binary Gap
    • Advantage Shuffle
    • Minimum Number of Refueling Stops
    • Reordered Power of 2
  • Dynamic Programming
    • Climbing Stairs
    • Range Sum Query - Immutable
    • Counting Bits
    • Arithmetic Slices
    • Palindromic Substrings
    • Minimum ASCII Delete Sum for Two Strings
    • Maximum Length of Pair Chain
    • Integer Break
    • Shopping Offers
    • Count Numbers with Unique Digits
    • 2 Keys Keyboard
    • Predict the Winner
    • Stone Game
    • Is Subsequence
    • Delete and Earn
    • Longest Palindromic Subsequence
    • Target Sum
    • Unique Binary Search Trees
    • Minimum Path Sum
    • Combination Sum IV
    • Best Time to Buy and Sell Stock with Cooldown
    • Largest Sum of Averages
    • Largest Plus Sign
    • Untitled
  • Invert Binary Tree
  • Intersection of Two Arrays
  • Surface Area of 3D Shapes
  • K Closest Points to Origin
  • Rotting Oranges
  • Smallest Integer Divisible by K
  • Duplicate Zeros
  • DI String Match
  • Implement Queue using Stacks
  • Increasing Order Search Tree
  • Reveal Cards In Increasing Order
  • Reshape the Matrix
  • Partition List
  • Total Hamming Distance
  • Validate Binary Search Tree
  • Decode Ways
  • Construct Binary Tree from Preorder and Inorder Traversal
  • Construct Binary Search Tree from Preorder Traversal
  • Design Circular Queue
  • Network Delay Time
  • Most Frequent Subtree Sum
  • Asteroid Collision
  • Binary Tree Inorder Traversal
  • Check If Word Is Valid After Substitutions
  • Construct Binary Tree from Preorder and Postorder Traversal
  • K-Concatenation Maximum Sum
Powered by GitBook
On this page
  • Description
  • Solutions
  • DFS
  • Dynamic programming
  1. Dynamic Programming

Target Sum

Description

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.

Solutions

DFS

Let dp[i, target] be the number of subsets of nums[i..] that sum up to target.

Then dp[i, target] = dp[i+1, target] + dp[i+1, target - nums[i]].

class Solution {
public:
    int findTargetSumWays(vector<int>& nums, int S) {
        int sum = 0;
        for(int num: nums){
            sum += num;
        }
        if(sum < S || (sum - S) % 2) return 0;
        return findTargetSumWays(nums, 0, (sum - S) / 2);
    }
    
    int findTargetSumWays(vector<int> &nums, int i, int target){
        if(target < 0)
            return 0;
        if(i == nums.size())
            return target == 0;
        return findTargetSumWays(nums, i + 1, target) + findTargetSumWays(nums, i + 1, target - nums[i]);
    }
};

Dynamic programming

Let dp[k, target] be the number of subsets of nums[0..k] that sum up to target.

Then dp[k+1, target] = dp[k, target] + dp[k, target - nums[i]].

Since dp[k+1, :] depends only on dp[k, :], we can optimize the algorithm to use an array of size n + 1, where n is the sum of integers with negative symbol.

class Solution {
public:
    int findTargetSumWays(vector<int>& nums, int S) {
        int sum = accumulate(nums.begin(), nums.end(), 0);
        if(sum < S || (sum - S) % 2) return 0;
        int target = (sum - S) / 2;
        vector<int> dp(target + 1, 0);
        dp[0] = 1;
        for(int n : nums)
            for(int i = target; i >= n; --i)
                dp[i] += dp[i - n];
        return dp[target];
    }
};

PreviousLongest Palindromic SubsequenceNextUnique Binary Search Trees

Last updated 6 years ago

Let ppp, nnn be the sums of numbers with positive and negative symbols, respectively. Let sum=p+nsum= p +nsum=p+n.

p−n=Sp−n+2n=S+2np+n=S+2nn=p+n−S2=sum−S2p=sum−n=sum+S2\begin{align} p - n &=S \\ p - n + 2n &= S + 2n \\ p + n &= S + 2n \\ n &= \frac{p+n-S}{2} =\frac{sum - S}{2} \\ p &= sum - n = \frac{sum+S}{2} \end{align}p−np−n+2np+nnp​=S=S+2n=S+2n=2p+n−S​=2sum−S​=sum−n=2sum+S​​​

Therefore, the problem is equivalent to finding integers that sum up to ppp or finding integers that sum up to nnn.