本文共 2609 字，大约阅读时间需要 8 分钟。

给你一个整数数组 nums 和一个整数 target 。

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

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

示例 1：

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

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

1.递归。每种情况都找到，然后计算出现次数即可。

class Solution {    int count = 0;        public int findTargetSumWays(int[] nums, int target) {        findTarget(nums,target,0,0);        return count;    }    public void findTarget(int[] nums,int target,int index,int sum) {        if (index == nums.length) {//当数组中所有元素都遍历过了            if (sum == target) {//如果此时sum等于目标值，就加1                count++;            }        } else {//还有没有遍历的元素            findTarget(nums,target,index + 1,sum + nums[index]);//取加号            findTarget(nums,target,index + 1,sum - nums[index]);//或者取负号        }    }}

2.题解：

        动态规划：转换为0-1背包问题。

class Solution {    public int findTargetSumWays(int[] nums, int target) {        int sum = 0;        for (int num : nums) {//计算数组的总和            sum += num;        }                //如果sum和小于target的绝对值，或者两者相加是奇数的话，肯定不存在，直接返回false        if (sum < Math.abs(target) ||(target + sum) % 2 == 1) {            return 0;        }        //转为0-1背包问题        int num = (target + sum) / 2;        int len = nums.length;        //dp[i][j]表示取i个数字，达到值j的组合次数        int[][] dp = new int[len + 1][num + 1];        dp[0][0] = 1;//边界初始化        for (int i = 1;i <= len;i++) {            for (int j = 0;j <= num;j++) {                if (j >= nums[i - 1]) {//当前值可以取的情况下                    //取当前值或者不取当前值的组合次数相加                    dp[i][j] = dp[i - 1][j] + dp[i - 1][j - nums[i - 1]];                } else {//不能取当前值的情况下                    dp[i][j] = dp[i - 1][j];                }            }        }        return dp[len][num];    }}

        可以发现当前行的状态只和上一行的状态有关，因此可以进行优化。

class Solution {    public int findTargetSumWays(int[] nums, int target) {        int sum = 0;        for (int num : nums) {//计算数组的总和            sum += num;        }                //如果sum和小于target的绝对值，或者两者相加是奇数的话，肯定不存在，直接返回false        if (sum < Math.abs(target) ||(target + sum) % 2 == 1) {            return 0;        }        //转为0-1背包问题        int w = (target + sum) / 2;        int len = nums.length;        //dp[j]表示达到值j的组合次数        int[] dp = new int[w + 1];        dp[0] = 1;//边界初始化        for (int num : nums) {            for (int j = w;j >= num;j--) {                dp[j] = dp[j] + dp[j - num];            }        }        return dp[w];    }}

题源：

转载地址：https://blog.csdn.net/xxyneymar/article/details/122274056 如侵犯您的版权，请留言回复原文章的地址，我们会给您删除此文章，给您带来不便请您谅解！