/ * *

The title

Given a non-empty array containing only positive integers. Is it possible to split this array into two subsets so that the sum of the elements in the two subsets is equal?

Note:

No more than 100 elements in each array] The size of the array does not exceed 200 example 1:

Input: [1, 5, 11, 5]

Output: true,

Explanation: Arrays can be split into [1, 5, 5] and [11].

Example 2:

Input: [1, 2, 3, 5]

Output: false

An array cannot be split into two elements and equal subsets.

Source: LeetCode link: leetcode-cn.com/problems/pa… Copyright belongs to the Collar buckle network. Commercial reprint please contact official authorization, non-commercial reprint please indicate the source.

The test code

print(canPartition([1, 5, 11, 5]))

notes

This is a classic 0-1 knapsack problem where you can only take each element once, and each time you’re looking for an optimal value between taking and not taking and you can see how that works in the code and in the notes

For 0-1 packs, check out this article: juejin.cn/post/684490…

The code address

Github.com/zmfflying/Z… * /

The problem solving code

Func canPartition(_ nums: [Int]) -> Bool {var sum = 0 for num in nums {sum += num} If sum % 2! If sum % 2! If sum % 2! = 0 {return false} Let C = sum / 2 let count = nums.count If there is a subset of the first I elements that is equal to and equal to j // note that the inner array is C+1, because count is not needed in the case of C, and the last element is count-1. [[Bool]] = [[Bool]].init(repeating: [Bool].init(repeating: false, count: C+1), count: count) Dp [I][0] is identical to true, because a subset of sum equal to 0 must exist, i.e. [] for I in 0.. <count { dp[i][0] = true } for i in 1.. <count { let num = nums[i] for j in 1... C {// if it is greater than j, If j < num {dp[I][j] = dp[i-1][j]} else {if j < num {dp[i-1][j] = dp[i-1][j]} True | | false = true / / so as long as there is a meet, That it is ok to dp [I] [j] = dp [j] [I - 1] | | dp [j - num] [I - 1]}}} return dp] [count - 1} [C] / / / / in view of the subject in terms of optimization of one dimensional array, dp is a bool type element, as long as there is a true / / so true | | false = true func canPartition1 (_ nums: [Int]) -> Bool { var sum = 0 for num in nums { sum += num } if sum % 2 ! = 0 { return false } let C = sum / 2 let count = nums.count var dp: [Bool] = [Bool].init(repeating: false, count: C+1) dp[0] = true for i in 1.. <count {let num = nums[I] // All d [0 + num] element to true the var while j j = C > num = {dp [j] = dp [j] | | dp [j - num] j - = 1}} return dp [C]}Copy the code