# Java and python DP solution O(nk)

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

Python

``````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():
temp[k-nums[i]]+=v
temp[k+nums[i]]+=v
prev = temp
return prev[S]
``````

JAVA

``````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]
if(i==0){
prev.put(nums[0], 1);
if(!prev.containsKey(-nums[0])){
prev.put(-nums[0], 1);
}else{
prev.put(-nums[0], 2); // if nums[0] is 0.
}
}else{
cur = new HashMap<Integer, Integer>();
for(Map.Entry<Integer, Integer> entry: prev.entrySet()){
int sumSoFar = entry.getKey();
int count = entry.getValue();
if(!cur.containsKey(sumSoFar+nums[i])){
cur.put(sumSoFar+nums[i], count);
}else{
cur.put(sumSoFar+nums[i], cur.get(sumSoFar+nums[i])+count);
}
// subtract num[i]
if(!cur.containsKey(sumSoFar-nums[i])){
cur.put(sumSoFar-nums[i], count);
}else{
cur.put(sumSoFar-nums[i], cur.get(sumSoFar-nums[i])+count);
}
}
prev = cur;
}
}
return prev.containsKey(S)? prev.get(S) : 0;
}
``````

• You claim this is O(n) in time?

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

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

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

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