offer2-102

给定一个正整数数组 nums 和一个整数 target 。

向数组中的每个整数前添加 '+' 或 '-' ，然后串联起所有整数，可以构造一个 表达式 ：

• 例如，nums = [2, 1] ，可以在 2 之前添加 '+' ，在 1 之前添加 '-' ，然后串联起来得到表达式 "+2-1" 。

返回可以通过上述方法构造的、运算结果等于 target 的不同 表达式 的数目。

示例 1：

输入：nums = [1,1,1,1,1], target = 3
输出：5
解释：一共有 5 种方法让最终目标和为 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

示例 2：

输入：nums = [1], target = 1
输出：1

提示：

• 1 <= nums.length <= 20
• 0 <= nums[i] <= 1000
• 0 <= sum(nums[i]) <= 1000
• -1000 <= target <= 1000

//leetcode submit region begin(Prohibit modification and deletion)
class Solution {
    public int findTargetSumWays(int[] nums, int target) {
        int sum = 0;

        if (nums == null || nums.length == 0) {
            return 0;
        }

        for (int num : nums) {
            sum += num;
        }

        if ((target > 0 && target > sum) || (target < 0 && target < (-sum))) {
            return 0;
        }

        int[][] dp = new int[nums.length][sum * 2 + 1];
        dp[0][convertNum(nums[0], sum)] += 1;
        dp[0][convertNum(-nums[0], sum)] += 1;

        for (int i = 1; i < nums.length; i++) {
            for (int j = 0; j <= sum; j++) {
                if (dp[i - 1][j] > 0) {
                    int origin = -j;

                    int added = origin + nums[i];
                    int minus = origin - nums[i];

                    dp[i][convertNum(added, sum)] += dp[i - 1][j];
                    dp[i][convertNum(minus, sum)] += dp[i - 1][j];
                }
            }

            for (int j = sum + 1; j < sum * 2 + 1; j++) {
                if (dp[i - 1][j] > 0) {
                    int origin = j - sum;

                    int added = origin + nums[i];
                    int minus = origin - nums[i];

                    dp[i][convertNum(added, sum)] += dp[i - 1][j];
                    dp[i][convertNum(minus, sum)] += dp[i - 1][j];
                }
            }
        }

        return dp[nums.length - 1][convertNum(target, sum)];
    }

    private int convertNum(int num, int sum) {
        if (num <= 0) {
            return -num;
        } else {
            return sum + num;
        }
    }
}
//leetcode submit region end(Prohibit modification and deletion)