# Java simple DFS with memorization

• 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);
}
}
``````

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

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

• 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?

• 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.

• @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.

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

• 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.

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

• 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.

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

``````return map.get(encodeString);
``````

• @tiandiao123
I think we execute this line some times but not that often.
For the haspmap, we can understand it as:
When we are in level i and got the sum of x, for the remaining numbers (from i+1 -> nums.length -1), how many ways do we have to get the target.

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