C# - recursive DFS with memorization


  • 1

    Here is use an array of Hash Tables where the index corresponds to the index within your search and each Hash Table uses the target as the key and count as the value.

    FYI - initially I did not use memorization and it was still AC although with a slow time - bottom 10%. I added the memorization and the time sped up into the top 25%.

        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;
            
            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;
        }
    

Log in to reply
 

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