494. Target Sum - Medium

前往題目

想法

• dp，但轉換方程不知道該拿什麼作為第一維，什麼作為第二維

思路

1. 利用memoization和dp
2. dp的一維是(目前在哪個index, 然後當前的總和是多少)，第二維就是該組合可以有幾種方式達成，也就是題目要求的結果
3. 從第0 index開始，檢查是否已經計算過，沒有的話繼續呼叫方法，index要加1，因為要看下一個了，而當前總和要減去當前的index的值
4. 把所有的狀況都列出來就可以算出答案

這題我用String來當作Pair使用，比較方便

Code

class Solution {
    // (index, remain) -> possibilities
    private Map<String, Integer> map;
    
    public int findTargetSumWays(int[] nums, int target) {
        map = new HashMap<>();
        return backtrack(nums, 0, target);
    }

    private int backtrack(int[] nums, int i, int remain) {
        // Reached the end
        if (i == nums.length) 
            // Decide if equals to the target
            return remain == 0 ? 1 : 0;
        
        String key = i + ", " + remain;
        
        // Check if already calculated
        if (map.containsKey(key)) {
            return map.get(key);
        }

        // Build all the possibilities
        map.put(key, backtrack(nums, i + 1, remain - nums[i]) +
                     backtrack(nums, i + 1, remain + nums[i]));
        
        return map.get(key);
    }
}