Movatterモバイル変換

[0]ホーム
URL:

Skip to content

Navigation Menu

Sign in
Appearance settings

Search code, repositories, users, issues, pull requests...

Provide feedback

We read every piece of feedback, and take your input very seriously.

Saved searches

Use saved searches to filter your results more quickly

 Sign up
Appearance settings

Create: 84-Largest-Rectangle-in-Histogram.ts, 4-Median-of-Two-Sorted-Arrays.ts, 25-Reverse-Nodes-in-k-Group.ts, 1899-Merge-Triplets-to-Form-Target-Triplet.ts, 10-Regular-Expression-Matching.ts, 134-Gas-Station.ts, 55-Jump-Game.ts, 45-Jump-Game-II.ts, 199-Binary-Tree-Right-Side-View.ts, 124-Binary-Tree-Maximum-Path-Sum.ts, 98-Validate-Binary-Search-Tree.ts, 678-Valid-Parenthesis-String.ts, 518-Coin-Change-II.ts, 97-Interleaving-String.ts, 115-Distinct-Subsequences.ts, 312-Burst-Balloons.ts, 105-Construct-Binary-Tree-from-Preorder-and-Inorder-Traversal.ts, 215-Kth-Largest-Element-in-an-Array.ts, 621-Task-Scheduler.ts, 994-Rotting-Oranges.ts, 210-Course-Schedule-II.ts, 207-Course-Schedule.ts, 684-Redundant-Connection.ts, 127-Word-Ladder.ts, 787-Cheapest-Flights-Within-K-Stops.ts, 494-Target-Sum.ts, 846-Hand-of-Straights.ts#1062

New issue

Have a question about this project? Sign up for a free GitHub account to open an issue and contact its maintainers and the community.

By clicking “Sign up for GitHub”, you agree to ourterms of service andprivacy statement. We’ll occasionally send you account related emails.

Already on GitHub?Sign in to your account

Merged
Ahmad-A0 merged 29 commits intoneetcode-gh:mainfromYkhan799:main
Sep 11, 2022
Merged

Create: 84-Largest-Rectangle-in-Histogram.ts, 4-Median-of-Two-Sorted-Arrays.ts, 25-Reverse-Nodes-in-k-Group.ts, 1899-Merge-Triplets-to-Form-Target-Triplet.ts, 10-Regular-Expression-Matching.ts, 134-Gas-Station.ts, 55-Jump-Game.ts, 45-Jump-Game-II.ts, 199-Binary-Tree-Right-Side-View.ts, 124-Binary-Tree-Maximum-Path-Sum.ts, 98-Validate-Binary-Search-Tree.ts, 678-Valid-Parenthesis-String.ts, 518-Coin-Change-II.ts, 97-Interleaving-String.ts, 115-Distinct-Subsequences.ts, 312-Burst-Balloons.ts, 105-Construct-Binary-Tree-from-Preorder-and-Inorder-Traversal.ts, 215-Kth-Largest-Element-in-an-Array.ts, 621-Task-Scheduler.ts, 994-Rotting-Oranges.ts, 210-Course-Schedule-II.ts, 207-Course-Schedule.ts, 684-Redundant-Connection.ts, 127-Word-Ladder.ts, 787-Cheapest-Flights-Within-K-Stops.ts, 494-Target-Sum.ts, 846-Hand-of-Straights.ts#1062

Changes from1 commit
Commits
Show all changes
29 commits
Select commitHold shift + click to select a range
1ad6706
Create: 84-Largest-Rectangle-in-Histogram.ts
Ykhan799Sep 6, 2022
07a3d4a
Create: 4-Median-of-Two-Sorted-Arrays.ts
Ykhan799Sep 6, 2022
1616f50
Add: 25-Reverse-Nodes-in-k-Group.ts
Ykhan799Sep 6, 2022
f9e95be
Create: 1899-Merge-Triplets-to-Form-Target-Triplet.ts
Ykhan799Sep 6, 2022
04066fa
Create: 10-Regular-Expression-Matching.ts
Ykhan799Sep 7, 2022
9ae6057
Merge branch 'neetcode-gh:main' into main
Ykhan799Sep 7, 2022
156bccb
Create: 134-Gas-Station.ts
Ykhan799Sep 7, 2022
7c67774
Create: 55-Jump-Game.ts
Ykhan799Sep 7, 2022
07753d0
Create: 45-Jump-Game-II.ts
Ykhan799Sep 7, 2022
ac3cef1
Create: 199-Binary-Tree-Right-Side-View.ts
Ykhan799Sep 7, 2022
c661398
Create: 124-Binary-Tree-Maximum-Path-Sum.ts
Ykhan799Sep 7, 2022
22ec063
Create: 98-Validate-Binary-Search-Tree.ts
Ykhan799Sep 7, 2022
e6a0eb7
Create: 678-Valid-Parenthesis-String.ts
Ykhan799Sep 8, 2022
9634ba8
Create: 518-Coin-Change-II.ts
Ykhan799Sep 8, 2022
4509f59
Create: 97-Interleaving-String.ts
Ykhan799Sep 8, 2022
b1a0f76
Create: 115-Distinct-Subsequences.ts
Ykhan799Sep 8, 2022
db4585a
Create: 312-Burst-Balloons.ts
Ykhan799Sep 8, 2022
62962a4
Create: 105-Construct-Binary-Tree-from-Preorder-and-Inorder-Traversal.ts
Ykhan799Sep 9, 2022
b740823
Create: 215-Kth-Largest-Element-in-an-Array.ts
Ykhan799Sep 10, 2022
aec310a
Create: 621-Task-Scheduler.ts
Ykhan799Sep 10, 2022
18e2450
Create: 994-Rotting-Oranges.ts
Ykhan799Sep 10, 2022
70a7c8e
Create: 210-Course-Schedule-II.ts
Ykhan799Sep 10, 2022
75af916
Create: 207-Course-Schedule.ts
Ykhan799Sep 10, 2022
03c5b10
Merge branch 'neetcode-gh:main' into main
Ykhan799Sep 10, 2022
1f08383
Create: 684-Redundant-Connection.ts
Ykhan799Sep 10, 2022
ba94b3f
Create: 127-Word-Ladder.ts
Ykhan799Sep 10, 2022
80e215d
Create: 787-Cheapest-Flights-Within-K-Stops.ts
Ykhan799Sep 11, 2022
c82a5cb
Create: 494-Target-Sum.ts
Ykhan799Sep 11, 2022
560f835
Create: 846-Hand-of-Straights.ts
Ykhan799Sep 11, 2022
File filter

Filter by extension

Filter by extension
Conversations
Failed to load comments.
Loading
Jump to
Jump to file
Failed to load files.
Loading
Diff view
Diff view
PrevPrevious commit
NextNext commit
Create: 494-Target-Sum.ts
  • Loading branch information
@Ykhan799
Ykhan799 authoredSep 11, 2022
commitc82a5cbe3e19075c3b871e8e47c4a75f55e686dc
29 changes: 29 additions & 0 deletionstypescript/494-Target-Sum.ts
View file
Open in desktop
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,29 @@
function findTargetSumWays(nums: number[], target: number): number {
// key: index, sum till index element, value: number of ways to get to that sum
const cache = new Map();

const backTrack = (i, sum) => {

/* if we're at the last element + 1 we compare the sum to our target
if it's true, we've found a way to our sum!
*/
if (i === nums.length) {
if (sum === target) {
return 1;
}
return 0;
}

// if already index, sum pair exist in our HashMap, we return the memoized result
if (cache.has(`${i},${sum}`)) {
return cache.get(`${i},${sum}`);
}

// DP: we memoize number of ways of each pair index, sum
cache.set(`${i},${sum}`, backTrack(i + 1, sum + nums[i]) + backTrack(i + 1, sum - nums[i]));

return cache.get(`${i},${sum}`);
};

return backTrack(0, 0);
};
[8]ページ先頭
©2009-2025 Movatter.jp