Java and python DP solution O(nk)

  • 0

    The idea is to keep all possible sums for nums[i] and generate all possible sums for nums[i+1] using + and -.


    def findTargetSumWays(self, nums, S):
            :type nums: List[int]
            :type S: int
            :rtype: int
            if len(nums)==0:
                return 0
            from collections import defaultdict
            prev = defaultdict(int)
            prev[nums[0]] += 1
            prev[-nums[0]] += 1
            for i in range(1, len(nums)):
                temp = defaultdict(int)
                for k,v in prev.items():
                prev = temp
            return prev[S]


    public int findTargetSumWays(int[] nums, int S) {
            if(nums.length==0) return 0;
            Map<Integer, Integer> prev = new HashMap<Integer, Integer>();;
            Map<Integer, Integer> cur;
            for(int i = 0; i< nums.length; i++){
                //for nums[0]
                    prev.put(nums[0], 1);
                        prev.put(-nums[0], 1);
                        prev.put(-nums[0], 2); // if nums[0] is 0.
                    cur = new HashMap<Integer, Integer>();
                    for(Map.Entry<Integer, Integer> entry: prev.entrySet()){
                        int sumSoFar = entry.getKey();
                        int count = entry.getValue();
                        // add num[i]
                             cur.put(sumSoFar+nums[i], count);
                             cur.put(sumSoFar+nums[i], cur.get(sumSoFar+nums[i])+count);
                         // subtract num[i]
                             cur.put(sumSoFar-nums[i], count);
                             cur.put(sumSoFar-nums[i], cur.get(sumSoFar-nums[i])+count);
                    prev = cur;
            return prev.containsKey(S)? prev.get(S) : 0;

  • 0

    You claim this is O(n) in time?

  • 0

    If this is O(n), you will win a Turing award!

  • 0

    @jedihy I apologize. It's O(nk) because HashMap size is also growing.

  • 0

    @varun37 No Problem. The time complexity I believe is O(nS) where S is the target.

Log in to reply

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