494. 目标和 (opens new window)

1.DFS搜索

每个元素都有两种运算方式，搜索每一个元素空间

class Solution {
    int res=0;
    public int findTargetSumWays(int[] nums, int target) {
        dfs(nums,target,0,0);
        return res;
    }
    public void dfs(int[] nums,int target,int index,int curr){
        if(index==nums.length-1){
            if(curr+nums[index]==target)
            res++;
            if(curr-nums[index]==target)
            res++;
            return;
        }
        dfs(nums,target,index+1,curr+nums[index]);
        dfs(nums,target,index+1,curr-nums[index]);

    }
}

进一步地，可以采用记忆化搜索进行优化，采用一个cache保存第i层搜索树当前和为curr的结果。

2.动态规划+背包

将原问题转化为从nums中取出n数，使其相加之和等于(target+numsSum)/2。

定义dp[ i ][ j ]表示考虑前i个元素，目标和为j的所有方案数。如果前i-1个状态的方案数不为0，则表示该状态可以达到。状态转移时包含两部分，一部分是前i-1已经达到 j 状态的方案数，另一部分是算入第 i 个数后能够达到的状态方案数。