# What is the time complexity of this?

• I have this solution. I think the time complexity is O(nS) but not sure. It looks like O(nS) isn't it?

``````public class Solution {
public int findTargetSumWays(int[] nums, int S) {
if(nums == null || nums.length == 0) {
return 0;
}
Map<Integer, Map<Integer, Integer>> map = new HashMap<>();

helper(nums, S, map, 0);

return map.get(0).get(S);
}

private int helper(int[] nums, int S, Map<Integer, Map<Integer, Integer>> map, int index) {
if(index == nums.length) {
if(0 == S) {
return 1;
} else {
return 0;
}
}
if(map.containsKey(index)) {
if(map.get(index).containsKey(S)) {
return map.get(index).get(S);
}
}

int count = 0;
count += helper(nums, S-nums[index], map, index+1);
count += helper(nums, S+nums[index], map, index+1);

Map<Integer,Integer> innerMap = map.getOrDefault(index, new HashMap<Integer,Integer>());
innerMap.put(S, count);
map.put(index, innerMap);

return count;

}
}
``````

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