Commit5ddaaff

committed

add: Partition Equal Subset Sum

1 parent2e1396b commit5ddaaffCopy full SHA for 5ddaaff

File tree

+46

-0

lines changed

+46

-0

lines changed

Lines changed: 1 addition & 0 deletions

Original file line number	Diff line number	Diff line change
`@@ -54,6 +54,7 @@ This is the solutions collection of my LeetCode submissions, most of them are pr`
`54`	`54`	`\|371\|[Sum of Two Integers](https://leetcode.com/problems/sum-of-two-integers/)\|[JavaScript](./src/sum-of-two-integers/res.js)\|Easy\|`
`55`	`55`	`\|384\|[Shuffle an Array](https://leetcode.com/problems/shuffle-an-array/)\|[JavaScript](./src/shuffle-an-array/res.js)\|Medium\|`
`56`	`56`	`\|404\|[Sum of Left Leaves](https://leetcode.com/problems/sum-of-left-leaves/)\|[JavaScript](./src/sum-of-left-leaves/res.js)\|Easy\|`
	`57`	`+\|416\|[Partition Equal Subset Sum](https://leetcode.com/problems/partition-equal-subset-sum/)\|[JavaScript](./src/partition-equal-subset-sum/res.js)\|Medium\|`
`57`	`58`	`\|434\|[Number of Segments in a String](https://leetcode.com/problems/number-of-segments-in-a-string/)\|[JavaScript](./src/number-of-segments-in-a-string/res.js)\|Easy\|`
`58`	`59`	`\|516\|[Longest Palindromic Subsequence](https://leetcode.com/problems/longest-palindromic-subsequence/)\|[JavaScript](./src/longest-palindromic-subsequence/res.js)\|Medium\|`
`59`	`60`	`\|523\|[Continuous Subarray Sum](https://leetcode.com/problems/continuous-subarray-sum/)\|[JavaScript](./src/continuous-subarray-sum/res.js)\|Medium\|`

Lines changed: 45 additions & 0 deletions

Original file line number	Diff line number	Diff line change
`@@ -0,0 +1,45 @@`
	`1`	`+/**`
	`2`	`+ * res.js`
	`3`	`+ *@authors Joe Jiang (hijiangtao@gmail.com)`
	`4`	`+ *@date 2017-04-12 21:44:08`
	`5`	`+ *`
	`6`	`+ * Given a non-empty array containing only positive integers, find if the array can be partitioned into two subsets such that the sum of elements in both subsets is equal.`
	`7`	`+ *`
	`8`	`+ * Note:`
	`9`	`+ * Each of the array element will not exceed 100`
	`10`	`+ * The array size will not exceed 200.`
	`11`	`+ *`
	`12`	`+ * Optimize Idea: https://discuss.leetcode.com/topic/67539/0-1-knapsack-detailed-explanation/2`
	`13`	`+ *`
	`14`	`+ *@param {number[]} nums`
	`15`	`+ *@return {boolean}`
	`16`	`+ */`
	`17`	`+letcanPartition=function(nums){`
	`18`	`+letlen=nums.length,`
	`19`	`+res=0;`
	`20`	`+if(len===1)returnfalse;`
	`21`	`+`
	`22`	`+// 求和`
	`23`	`+for(leti=0;i<len;i++){`
	`24`	`+res+=nums[i];`
	`25`	`+}`
	`26`	`+if(res%2)returnfalse;`
	`27`	`+res/=2;`
	`28`	`+`
	`29`	`+// 初始化结果数组,所有元素初始化为0`
	`30`	`+letarr=newArray(res+1);`
	`31`	`+arr[0]=1;`
	`32`	`+for(leti=1;i<=res;i++){`
	`33`	`+arr[i]=0;`
	`34`	`+}`
	`35`	`+`
	`36`	`+// 遍历 nums 数组更新 arr`
	`37`	`+for(leti=0;i<len;i++){`
	`38`	`+for(letj=res;j>=nums[i];j--){`
	`39`	`+arr[j]+=arr[j-nums[i]];`
	`40`	`+}`
	`41`	`+if(arr[res])returntrue;`
	`42`	`+}`
	`43`	`+`
	`44`	`+returnfalse;`
	`45`	`+};`

Comments

(0)