题目分析

本题也是一个非常有趣的题目，很容易想到回溯法进行求解，但是时间复杂度为$O(2^n)$，对于数据量稍大的场景都无法适用。小伙伴们思考是否还要其他的方法？

动态规划

如果数据量较大，又没有特殊方法的题目，小伙伴们思路可以向动态规划靠近。

本题的要求是从前n个数，进行组合找到和为target的数。因此存在最优子问题，假设最后一个数为k，那么最优子问题等价于从前n - 1个数，组合找到和为target - k或者target + k的结果之和。用dp[i][j]代表前i个数之和为j的表达式数目。

$$dp[i][j] = dp[i - 1][j - nums[i]] + dp[i - 1][j + nums[i]]$$

算法的时间复杂度为$O(n \cdot target)$，空间复杂度为$O(n \cdot target)$

下面是C++语言的题解

class Solution {
public:
    int findTargetSumWays(vector<int>& nums, int target) {
        vector<vector<int>> dp(nums.size() + 1, vector<int>(2001));
        dp[0][1000] = 1;
        for (int i = 0; i < nums.size(); i++) {
            for (int j = -1000; j <= 1000; j++) {
                if (j + nums[i] >= -1000 && j + nums[i] <= 1000) { dp[i + 1][j + nums[i] + 1000] += dp[i][j + 1000]; }
                if (j - nums[i] >= -1000 && j - nums[i] <= 1000) { dp[i + 1][j - nums[i] + 1000] += dp[i][j + 1000]; }
            }
        }
        return dp.back()[target + 1000];
    }
};

下面是Kotlin语言的题解

class Solution {
    fun findTargetSumWays(nums: IntArray, target: Int): Int {
        val dp = Array(nums.size + 1) {IntArray(2001)}
        dp[0][1000] = 1
        for ((idx, x) in nums.withIndex()) {
            for (i in -1000..1000) {
                if (i + x >= -1000 && i + x <= 1000) { dp[idx + 1][i + x + 1000] += dp[idx][i + 1000]}
                if (i - x >= -1000 && i - x <= 1000) { dp[idx + 1][i - x + 1000] += dp[idx][i + 1000]}
            }
        }
        return dp[nums.size][target + 1000]
    }
}

优化动态规划

上面这种做法已经可以满足面试笔试的需求，但是本题有一种更巧妙的方法，转化为0-1背包问题进行求解。

因为nums都是正数，假设将其全部相加结果为sums，如果在某些位置加上负号，令这些数字之和为neg，所以其余的正数之和为sums - neg，此时整体数组之和为sums - neg + (-neg) = sums - 2neg = target。所以
$$neg = \frac{sums - target}{2}$$
即我们从nums中找出和为neg的子集数量即可，可以采用0-1背包的问题进行求解。用dp[i][j]表示前i个数和为j的子集数量。
$$dp[i][j] = max(dp[i - 1][j], dp[i - 1][j - nums[i]])$$
因为第i层状态仅与第i - 1层有关，可以使用一维dp进行求解。

算法的时间复杂度为$O(n \cdot (sum - target))$，空间复杂度为$O(sum - target)$

下面是C++语言的题解

class Solution {
public:
    int findTargetSumWays(vector<int>& nums, int target) {
        int sums = 0;
        for (int x : nums) { sums += x; }
        int diff = sums - target;
        if (diff < 0 || diff & 1) { return 0; }
        int neg = diff >> 1;
        vector<int> dp(neg + 1);
        dp[0] = 1;
        for (int i = 0; i < nums.size(); i++) {
            for (int j = neg; j >= nums[i]; j--) {
                dp[j] += dp[j - nums[i]];
            }
        }
        return dp.back();
    }
};

下面是Kotlin语言的题解

class Solution {
    fun findTargetSumWays(nums: IntArray, target: Int): Int {
        var sums = 0
        for (x in nums) { sums += x }
        val diff = sums - target
        if (diff < 0 || diff.and(1) == 1) { return 0 }
        val neg = diff.shr(1)
        val dp = IntArray(neg + 1)
        dp[0] = 1
        for (x in nums) {
            for (i in neg downTo x) {
                dp[i] += dp[i - x]
            }
        }
        return dp.last()
    }
}

对比C++和Kotlin两种语言，可以看出C++语言中布尔类型就是0和1，可以直接将运算结果进行布尔判断，而Kotlin布尔和整型不可以直接运算。而且在位操作时，C++是使用位运算符进行操作，如a&b，Kotlin使用成员方法进行操作，如a.and(b)或者a and b。

刷题总结

本题的重点是动态规划思路，并不是说优化的DP比普通的DP更好，小伙伴们要进行对比，将两者方法都掌握。