1、前言

2、思路

此题类似于二叉树搜索，写法比较简单。因为后面需要 sum 有复数，所以用数组作为 memo 只能继续非负整数部分，整数部分被忽略。如果比较在意时间，那么用 hashmap 来做（字符串拼接不也耗时吗？），如果不是，那么直接用数组记录即可。

3、代码

public class Q494_FindTargetSumWays {

    public int findTargetSumWays(int[] nums, int target) {
        if(nums == null || nums.length == 0){
            return 0;
        }

        Map<String, Integer> memo = new HashMap<>();
        return dfs(nums, target, 0, 0, memo);
    }

    private int dfs(int[] nums, int target, int sum, int i, Map<String, Integer> memo) {
        if(i == nums.length){
            return sum == target ? 1 : 0;
        }

        String key = i + "_" + sum;
        if(memo.containsKey(key)){
            memo.get(key);
        }

        int res = 0;
        res += dfs(nums, target, sum + nums[i], i + 1, memo);
        res += dfs(nums, target, sum - nums[i], i + 1, memo);

        memo.put(key, res);

        return res;
    }

    public static void main(String[] args) {
        System.out.println(new Q494_FindTargetSumWays().findTargetSumWays(new int[]{1}, 1));
    }
}