494. 目标和

回溯（耗时大）：

class Solution {
    int ans=0;
    public int findTargetSumWays(int[] nums, int target) {
   dfs(nums,0,target,0);
   return ans;
    }
    void dfs(int[] nums,int pos,int target,int sum){
        if(pos==nums.length){
             if(target==sum)
             ans++;
            return;
        }
        
        sum+=nums[pos];
        
        dfs(nums,pos+1,target,sum);
        sum-=2*nums[pos];
        dfs(nums,pos+1,target,sum);


    }
}

记忆化递归：

class Solution {
    //由递归转化成记忆化递归：
    //在考虑加入「记忆化」时，我们只需要将 DFS 方法签名中的【可变】参数作为维度，DFS 方法中的返回值作为存储值即可。
    //可用数组或者map作为记忆容器
    HashMap<String,Integer> map=new HashMap<>();
    public int findTargetSumWays(int[] nums, int target) {
         
         return dfs(nums,target,0,0);

    }
    int  dfs(int[] nums,int target,int pos,int sum){
          if(pos==nums.length){
              if(sum==target)
                   return 1;
            return 0;
          }
         String str=pos+"_"+sum;
         if(map.containsKey(str))return map.get(str);
         int res=dfs(nums,target,pos+1,sum+nums[pos])+dfs(nums,target,pos+1,sum-nums[pos]);
         map.put(str,res);
         return res;


    }
}

494. 目标和

原文：https://www.cnblogs.com/wsshub/p/15063927.html