What is the time complexity of this?


  • 0
    S

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

Log in to reply
 

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