链接：https://leetcode.cn/problems/target-sum/solution/by-xun-ge-v-gmb5/
来源：力扣（LeetCode）
著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。 

题目

示例

思路

解题思路

1. 深度优先搜索

看到题目容易想到的就是dfs暴力枚举每一个元素，每个元素都存在两种情况

• 为正数-->加上之前枚举的情况
• 为负数-->减去之前枚举的情况

最后当枚举到最后一个元素时判断是否满足条件，满足+1，不满足+0。

2. 动态规划，转换为0 1背包问题

题目需要分割非空数组 nums 为两个数组，这个数组分割使得两个子集的元素和相等。
可以将题目转换一下为，将nums数组求和之后，除半，再在数组nums中是否可以寻找任意个元素累加和相等，元素唯一不重复选择
其实将题目转换之后和 零钱兑换 题目思路就差不多了。都是背包问题
相当于现在给我们一个容量有限背包和一堆东西，我们需要将这些东西装到背包里面，现在只需要判断能不能正好装满，我不关心里面装什么，装多少。
所以我们申请二维dp[i][j]数组，记录我们这个背包装了什么还能装什么，装没有装满，遇见东西时就有两个状态

1. 没有装：

• dp[i][j] = dp[i-1][j]，没有装我继承上一次背包状态

2. 装了:

• 正好装满dp[i][j] = true
• 装了但是还没有装满：dp[i][j] = dp[i-1][j-nums[i]],东西我装了，判断一下我装了这个东西还有没有东西和我一起凑满

比如现在背包大小为5，有东西1,2,3,4(与题目无关)，dp[i][j]表示背包大为j时，选择了东西i，当前背包是满(true),还是未满(false)，所以dp[1][2]为true，表示我选择了东西2并且背包大小为2时，我背包满了，因此dp[2][3]=true，那么dp[2][5] = dp[2][3] + dp[1][2] = true，我背包大小为5，可以选择装东西3和东西2，当背包大小不能装下我的东西时继承i-1背包状态，因为我可以选择不装当前东西，那么背包也就没有变动，以此类推，最后返回dp[][max_j] 是否满
空间压缩
从上面可以看出来，我们并不关心背包里面装了什么地方，那么是不是没必要申请记录装东西的大小，当然是可以的，我们只关心背包能不能装满，因此我们申请dp[n]记录背包大小为n时能不能装满，但是在装东西的时候就需要从大背包开始装，因为这样可以保留上一次背包状态

总和必须为偶数，奇数/2 存在.5我们不管怎么找都不能在整数数组中找到小数

代码

深度优先搜索

/*
*int findTargetSumWays(int* nums, int numsSize, int target)
int findTargetSumWays：数组中不同表达式值等于目标值的次数
int* nums：数组
int numsSize：数组长度
int target:目标值
返回值：有效表达式的数目
*/
int dfs(int * nums, int inode, int numsSize, int sum, int target)
{
    if(inode == numsSize){//枚举到最后一个元素
        if(sum == target){//有效表达式，满足题目要求
            return 1;
        }
        else{//不满足
            return 0;
        }
    }
    return dfs(nums, inode+1, numsSize, sum+nums[inode], target) + dfs(nums, inode+1, numsSize, sum-nums[inode], target);//累加所有情况
}
int findTargetSumWays(int* nums, int numsSize, int target){
    return dfs(nums, 0, numsSize, 0, target);//深度优先搜索枚举所有元素
}
 
作者：xun-ge-v
链接：https://leetcode.cn/problems/target-sum/solution/by-xun-ge-v-gmb5/
来源：力扣（LeetCode）
著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。

动态规划，转换为0 1背包问题

/*
*int findTargetSumWays(int* nums, int numsSize, int target)
int findTargetSumWays：数组中不同表达式值等于目标值的次数
int* nums：数组
int numsSize：数组长度
int target:目标值
返回值：有效表达式的数目
*/
int findTargetSumWays(int* nums, int numsSize, int target){
    int sum = 0;
    for(int i = 0; i < numsSize; i++)//求和
    {
        sum += nums[i];
    } 
    int diff = sum-target;
    if(diff < 0 || diff % 2 != 0)//特殊情况
    {
        return 0;
    }
    int n = diff/2;
    int dp[n+1];
    memset(dp, 0, sizeof(int) * (n + 1));
    dp[0] = 1;
    for(int i = 0; i < numsSize; i++)//枚举东西
    {
        for(int j = n; j >= nums[i]; j--)//更新背包
        {
            dp[j] += dp[j - nums[i]];
        }
    }
    return dp[n];
}
 
 
作者：xun-ge-v
链接：https://leetcode.cn/problems/target-sum/solution/by-xun-ge-v-gmb5/
来源：力扣（LeetCode）
著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。

时间空间复杂度