# Java solution with list and map

• This problem can be treated as a problem to find the number of paths to a destination island.

• Each possible sum is one island
• Our goal is to count the number of paths from island `0` to island `S`
``````public class Solution {
public int findTargetSumWays(int[] nums, int S) {

int n = nums.length;
if (n == 0) return 0;

// Map<current sum, number of ways to current sum>
List<Map<Integer, Integer>> dp = new ArrayList<>(n);

if (nums[0] == 0) {
// 0 is the corner case
dp.get(0).put(nums[0], 2);
} else {
dp.get(0).put(-nums[0], 1);
dp.get(0).put(nums[0], 1);
}

for (int i=1; i<n; ++i) {
Map<Integer, Integer> curMap = new HashMap<>();
Map<Integer, Integer> preMap = dp.get(i-1);

for (Map.Entry<Integer, Integer> entry : preMap.entrySet()) {
int sumPlus = entry.getKey() + nums[i];
int curNum = curMap.containsKey(sumPlus) ? curMap.get(sumPlus) : 0;
curMap.put(sumPlus, entry.getValue() + curNum);

int sumMinus = entry.getKey() - nums[i];
curNum = curMap.containsKey(sumMinus) ? curMap.get(sumMinus) : 0;
curMap.put(sumMinus, entry.getValue() + curNum);
}

}

Integer result = dp.get(n-1).get(S);
if (result == null) {
result = 0;
}

return result;
}
}
``````

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