ðŸ¥ˆ

# Partition Equal Subset Sum

Created
2021/12/12 03:09
ë¬¸ì œ ë²ˆí˜¸
416
ì¹´í…Œê³ ë¦¬
Array
Dynamic Programming

### Code

 .css-15tnwsa{max-width:100%;width:100%;white-space:pre-wrap;word-break:break-word;padding:7px 9px;background-color:transparent;font-size:14px;line-height:20px;min-height:1em;}.css-15tnwsa:empty::after{content:" ";}ì œì¶œ ë‚ ì§œ ì‹œê°„ ë©”ëª¨ë¦¬ 2021/12/12 11 ms 2.8 MB
// 416. Partition Equal Subset Sum // // https://leetcode.com/problems/partition-equal-subset-sum/ // // When the numbers are given, make two partitions such that each summation is equal. // Numbers will be given with the only positive integers, and non-empty array. // canPartition function checks the given numbers can be grouped or not. // When 2 groups which summations are equal, it implies that total summation is even. // After that, this function get the truth of each number whether it can be made with the element of the given array or not. // In the outer loop, the element of the array has been used in sequence. // To get the truth whether the number can be made, decrement inner loop has been used. // -> when the given array is [ 1, 2, 3, 5, 11 ] // -> first : 1 by dp[0] (using 1) // -> second : 1, 2, 3 by dp[0], dp[1] (using 2) // -> third : 1, 2, 3, 4, 5, 6 by dp[0] to dp[3] (using 3) // -> ... func canPartition(nums []int) bool { size := len(nums) acc := 0 for i := 0; i < size; i++ { acc += nums[i] } if acc%2 == 1 { return false } goal := acc / 2 dp := make([]bool, acc+1) dp[0] = true for i := 0; i < size; i++ { for j := goal; j >= nums[i]; j-- { dp[j] = dp[j] || dp[j-nums[i]] } } return dp[goal] }
Go
ë³µì‚¬