回溯（耗时大）：
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;
}
}