Java simple DFS with memorization


  • 28
    B

    I'm quite surprised that simple DFS could pass the test since for DFS solution there are obvious a lot of overlap subproblems. So I used a map to record the intermediate result while we are walking along the recursion tree.

    public class Solution {
        public int findTargetSumWays(int[] nums, int S) {
            if (nums == null || nums.length == 0){
                return 0;
            }
            return helper(nums, 0, 0, S, new HashMap<>());
        }
        private int helper(int[] nums, int index, int sum, int S, Map<String, Integer> map){
            String encodeString = index + "->" + sum;
            if (map.containsKey(encodeString)){
                return map.get(encodeString);
            }
            if (index == nums.length){
                if (sum == S){
                    return 1;
                }else {
                    return 0;
                }
            }
            int curNum = nums[index];
            int add = helper(nums, index + 1, sum - curNum, S, map);
            int minus = helper(nums, index + 1, sum + curNum, S, map);
            map.put(encodeString, add + minus);
            return add + minus;
        }
    }
    

  • 2
    L

    Brilliant solution!
    Get one question, what you think about the complexity after memorization? Thanks.


  • 0

    same here in C#, but I think it's going to be more efficient to use and array of Hashes where the array index corresponds to the recursive index and the found Hash uses the target for the key. This will avoid string manipulation and string hashing which are both going to slow you down.

        public int FindTargetSumWays(int[] nums, int S) 
        {
            Dictionary<int,int>[] map = new Dictionary<int,int>[nums.Length];
            for (int i = 0; i < nums.Length; i++) map[i] = new Dictionary<int,int>();
            
            return Find(nums, 0, S, map);
        }
        
        public int Find(int[] nums, int index, int target, Dictionary<int,int>[] map)
        {
            if (index == nums.Length)
            {
                return (target == 0) ? 1 : 0;
            }
            else
            {
                if (map[index].ContainsKey(target)) return map[index][target];
                
                int cnt = Find(nums, index + 1, target - nums[index], map) 
                            + Find(nums, index + 1, target + nums[index], map);
                
                map[index][target] = cnt;
                return cnt;
            }
        }
    

  • 0
    G

    I come up with the same idea. But what is the time complexity for this method? I'm always confused about the complexity analysis when using memorization. Can anyone tell me?


  • 0
    F

    Nice solution! One nitpick, the optimization technique is called memoization, not memorization.

    I did a similar solution but with a 2D array instead of a map, which was a little clunky because of handling negatives. Made the array twice the size that was needed and had one half for positives other for negatives.


  • 2
    G

    @GaoLiaoLiao Time complexity is definitely larger than pure DP where you store complete info of sum for each slice of array. In this solution, the subproblem is not that "sub". And in some worst cases, I think close to pure DFS.


  • 0
    G

    @guolei329 Thanks for your for explanation! (But I still don't know how to analyze the time complexity of this method.)


  • 0
    N

    I believe time complexity is 2^n. 'n' being the number of elements in the initial array. Let me explain...,

    Time complexity is same as DFS which is O(V+E).
    Now we need to calculate the number of vertices and edges.
    Consider the following example

    nums = [1,2,3]

    Let's draw out the tree structure

                                      Root 
                                      / \
                                   +1    -1
                                   /\     /\
                                 +2 -2  +2  -2
                                 /\  /\ /\  /\
                               +3 -3 ...  +3 -3
    

    So number of nodes = 15 = 2 ^ (3+1) - 1 = 2^(n+1) - 1 = O(2^n)
    number of edges = 14 = ... = O(2^n)

    so O(V+E) = O(2^n + 2^n) = O(2^n)

    And I believe space complexity to be O(n).

    Please correct me if I am wrong.


  • 1
    S

    @nagaraja This should be the worst case, where no item in the memorization map was used again.


  • 0

    @butzhang said in Java simple DFS with memorization:

    there are obvious a lot of overlap subproblems

    nice coding. But I do not think there are obvious a lot of overlap subproblems if you take worst case into consideration.


  • 1
    T

    I don't think using memoization really helps efficiency in this case, since we never execute the code:

    return map.get(encodeString);
    

Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.