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

Commite9e3ea4

Browse files
vedas-dixitgithub-actionsappgurueu
authored
Implemented Partition Problem, Recursive problem (TheAlgorithms#1582)
* Add Tug of War solution using backtracking* Updated Documentation in README.md* Added Tug of war problem link* Updated Documentation in README.md* Updated Documentation in README.md* Refactor tugOfWar: remove unused vars, optimize initialization, and remove redundant checks* Added Function Export Statment* Updated Documentation in README.md* Resolved Code Style --Prettier* Rename "backtrack" to "recurse"* Fix test case: The difference needs to be exactly 1.* Code Modification: subsets should have sizes as close to n/2 as possible* Updated test-case of TugOfWar* Changed TugOfWar problem to Partition* Modified partition problem* Updated Documentation in README.md* fixed code style---------Co-authored-by: github-actions <${GITHUB_ACTOR}@users.noreply.github.com>Co-authored-by: Lars Müller <34514239+appgurueu@users.noreply.github.com>
1 parenta044c57 commite9e3ea4

File tree

3 files changed

+65
-0
lines changed

3 files changed

+65
-0
lines changed

‎DIRECTORY.md

Lines changed: 2 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -160,6 +160,7 @@
160160
*[NumberOfIslands](Graphs/NumberOfIslands.js)
161161
*[PrimMST](Graphs/PrimMST.js)
162162
***Hashes**
163+
*[MD5](Hashes/MD5.js)
163164
*[SHA1](Hashes/SHA1.js)
164165
*[SHA256](Hashes/SHA256.js)
165166
***Maths**
@@ -300,6 +301,7 @@
300301
*[KochSnowflake](Recursive/KochSnowflake.js)
301302
*[LetterCombination](Recursive/LetterCombination.js)
302303
*[Palindrome](Recursive/Palindrome.js)
304+
*[Partition](Recursive/Partition.js)
303305
*[SubsequenceRecursive](Recursive/SubsequenceRecursive.js)
304306
*[TowerOfHanoi](Recursive/TowerOfHanoi.js)
305307
***Search**

‎Recursive/Partition.js

Lines changed: 39 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,39 @@
1+
/**
2+
*@function canPartition
3+
*@description Check whether it is possible to partition the given array into two equal sum subsets using recursion.
4+
*@param {number[]} nums - The input array of numbers.
5+
*@param {number} index - The current index in the array being considered.
6+
*@param {number} target - The target sum for each subset.
7+
*@return {boolean}.
8+
*@see [Partition Problem](https://en.wikipedia.org/wiki/Partition_problem)
9+
*/
10+
11+
constcanPartition=(nums,index=0,target=0)=>{
12+
if(!Array.isArray(nums)){
13+
thrownewTypeError('Invalid Input')
14+
}
15+
16+
constsum=nums.reduce((acc,num)=>acc+num,0)
17+
18+
if(sum%2!==0){
19+
returnfalse
20+
}
21+
22+
if(target===sum/2){
23+
returntrue
24+
}
25+
26+
if(index>=nums.length||target>sum/2){
27+
returnfalse
28+
}
29+
30+
// Include the current number in the first subset and check if a solution is possible.
31+
constwithCurrent=canPartition(nums,index+1,target+nums[index])
32+
33+
// Exclude the current number from the first subset and check if a solution is possible.
34+
constwithoutCurrent=canPartition(nums,index+1,target)
35+
36+
returnwithCurrent||withoutCurrent
37+
}
38+
39+
export{canPartition}

‎Recursive/test/Partition.test.js

Lines changed: 24 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,24 @@
1+
import{canPartition}from'../Partition'
2+
3+
describe('Partition (Recursive)',()=>{
4+
it('expects to return true for an array that can be partitioned',()=>{
5+
constresult=canPartition([1,5,11,5])
6+
expect(result).toBe(true)
7+
})
8+
9+
it('expects to return false for an array that cannot be partitioned',()=>{
10+
constresult=canPartition([1,2,3,5])
11+
expect(result).toBe(false)
12+
})
13+
14+
it('expects to return true for an empty array (0 elements)',()=>{
15+
constresult=canPartition([])
16+
expect(result).toBe(true)
17+
})
18+
19+
it('Throw Error for Invalid Input',()=>{
20+
expect(()=>canPartition(123)).toThrow('Invalid Input')
21+
expect(()=>canPartition(null)).toThrow('Invalid Input')
22+
expect(()=>canPartition(undefined)).toThrow('Invalid Input')
23+
})
24+
})

0 commit comments

Comments
 (0)
[8]ページ先頭
©2009-2025 Movatter.jp