494-目标和

LeetCode 494. Target Sum

LeetCode-494

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

method 1: 动态规划

把nums分成两堆，一堆left，一堆right，left都给正号，right都给负号，所以left-right=target，又因为left+right=sum是固定的，所以有left-(sum-left)=target，即left=(target+sum)/2

dp[j]：填满容量为j的背包有dp[j]种填法

转化为容量为(target+sum)/2的背包有多少种装法，例如容量为3的背包有dp[3]种装法，又来了一个weight[i]=2，则容量为5的背包的装法应该加上dp[5-weight[i]]=dp[3]，多一个物品nums[i]，就会多dp[j-nums[i]]种装法

求装满背包有几种方法，一般公式都是：dp[j] += dp[j - nums[i]]

使用滚动数组，外层遍历物品nums[i]，内层逆序遍历背包

初始化：dp[0]=1，装满容量为0的背包，有1种装法，就是放0个物品

int findTargetSumWays(vector<int>& nums, int target) {
    int sum = 0;
    for (auto n : nums) sum += n;
    if (abs(target) > sum) return 0;    // 全都给正号或负号也不行
    if ((target + sum) % 2) return 0;   // 一奇一偶不行
    int bagSize = (target + sum) / 2;
    vector<int> dp(bagSize + 1);
    dp[0] = 1;
    for (int i = 0; i < nums.size(); i++) {     // 遍历物品
        for (int j = bagSize; j >= nums[i]; j--) {  // 逆序遍历背包
            dp[j] += dp[j - nums[i]];
        }
    }
    return dp[bagSize];
}

如果sum是奇数，不管怎么组合都组合不出偶数，sum是奇数也组合不出偶数

method 2: 回溯

每个数有2种选择，要么加，要么减

int res;
void dfs(vector<int>& nums, int index, int target) {
    if (index == nums.size()) {
        if (target == 0) res++;
        return;
    }
    dfs(nums, index + 1, target - nums[index]);
    dfs(nums, index + 1, target + nums[index]);
}
int findTargetSumWays(vector<int>& nums, int target) {
    dfs(nums, 0, target);
    return res;
}