Commitc82a5cb

authored

Create: 494-Target-Sum.ts

1 parent80e215d commitc82a5cbCopy full SHA for c82a5cb

File tree

+29

-0

lines changed

+29

-0

lines changed

Lines changed: 29 additions & 0 deletions

Original file line number	Diff line number	Diff line change
`@@ -0,0 +1,29 @@`
	`1`	`+functionfindTargetSumWays(nums:number[],target:number):number{`
	`2`	`+// key: index, sum till index element, value: number of ways to get to that sum`
	`3`	`+constcache=newMap();`
	`4`	`+`
	`5`	`+constbackTrack=(i,sum)=>{`
	`6`	`+`
	`7`	`+/* if we're at the last element + 1 we compare the sum to our target`
	`8`	`+ if it's true, we've found a way to our sum!`
	`9`	`+ */`
	`10`	`+if(i===nums.length){`
	`11`	`+if(sum===target){`
	`12`	`+return1;`
	`13`	`+}`
	`14`	`+return0;`
	`15`	`+}`
	`16`	`+`
	`17`	`+// if already index, sum pair exist in our HashMap, we return the memoized result`
	`18`	+if(cache.has(`${i},${sum}`)){
	`19`	+returncache.get(`${i},${sum}`);
	`20`	`+}`
	`21`	`+`
	`22`	`+// DP: we memoize number of ways of each pair index, sum`
	`23`	+cache.set(`${i},${sum}`,backTrack(i+1,sum+nums[i])+backTrack(i+1,sum-nums[i]));
	`24`	`+`
	`25`	+returncache.get(`${i},${sum}`);
	`26`	`+};`
	`27`	`+`
	`28`	`+returnbackTrack(0,0);`
	`29`	`+};`

Comments

(0)