-
Notifications
You must be signed in to change notification settings - Fork 1
/
PositiveNegativeTargetSum_3.ts
61 lines (52 loc) · 2.66 KB
/
PositiveNegativeTargetSum_3.ts
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
/**
* Problem: Given an array of postive numbers, and a target sum 'S', assign each number a positive or a negative sign such that the total sum becomes the target sum S.
* Solution: Brute force will create all possible combinations of the numbers with a positive and negative signs. It means that each number will have 2 choices
* to pick up the number, a positive or a negative sign. Dynamic Programming will save and use existing results.
*
* Complexity: Time Complexity would be O(N * S) where N is all the numbers and S is not the target sum, but the sum of all the numbers (*2 since in worst case all negative will also be computed.)
* Complexity: Space: O(N * S) + O(N) since recursion will take a depth of N at max and O(N*S) space will be used by memoization.
*
* @param nums
* @param sum
*
* Total Sum: 11, TS: 13
* AD: 2
* Negative: 2, Positive: TS
* Positive: 2, Negative: TS
*
* Case 1: TaS > ToS: Nothing can happen.
* Case 2: TaS <= ToS: ToS - X -X = TaS?
* X = (ToS - TaS)/2
*
*
* Solution is based on the fact that a set of numbers should be found that can be used as a negative numbers to achieve the target sum
* using the total sum. These set of numbers (sum) would be deducted twice from the total sum as described above.
*/
function positiveNegativeTargetSumDP1(nums: number[], targetSum: number) {
// Calculate the range of maximum sum that can be achieved from the numbers.
const totalSum = nums.reduce((sum, val) => sum + val, 0);
const negationSum = (Math.abs(targetSum - totalSum))/2;
// Create a DP table for bottom up execution and storage of results.
const dp: number[][] = Array.from({length: nums.length}, () => Array(negationSum + 1).fill(0))
for (let idx = 0; idx < nums.length; idx++) {
dp[idx][0] = 1
}
for (let s = 1; s <= negationSum; s++) {
dp[0][s] = (nums[0] === s) ? 1 : 0
}
for (let idx = 1; idx < nums.length; idx++) {
for (let s = 1; s <= negationSum; s++) {
// At each iteration to achieve the target sum using the given index of the item of the set.
// We can either include the item in the target set or not include the item itself.
if (s >= nums[idx])
dp[idx][s] = dp[idx - 1][s - nums[idx]]
dp[idx][s] += dp[idx - 1][s]
}
}
return dp[nums.length - 1][negationSum];
}
function testPositiveNegativeTargetSumDP1(nums: number[], sum: number) {
console.log(`Total Count for positive negative target sum for input: ${nums} and target sum: ${sum} = ${positiveNegativeTargetSumDP1(nums, sum)}`)
}
testPositiveNegativeTargetSumDP1([1, 1, 2, 3], 1)
testPositiveNegativeTargetSumDP1([1, 2, 7, 1], 9)