How to divide equal sum subset by python

This article mainly explains "how to divide the equal and subset of python". The content of the explanation in the article is simple and clear, and it is easy to learn and understand. Please follow the editor's train of thought to study and learn "how to divide python into equal and subset".

Topic: dividing equal sum subset

Given a non-empty array that contains only positive integers. Whether it is possible to split the array into two subsets so that the sum of the elements of the two subsets is equal.

Note:

There are no more than 100 elements in each array

The size of the array will not exceed 200

Example 1:

Enter: [1, 5, 11, 5]

Output: true

Explanation: arrays can be divided into [1, 5, 5] and [11].

Example 2:

Enter: [1, 2, 3, 5]

Output: false

Explanation: an array cannot be divided into two elements and an equal subset.

Solve the problem:

The problem follows the dp. The array is divided into equal and subsets, that is, the sum of any element is equal to half of the sum of the array. Using the dp array, the I element indicates whether the sum of any element can be equal to I. Then if any dp [I] (n is any element of nums) is True, dp [I] is True.

Code

Class Solution:

Def canPartition (self, nums: List [int])-> bool:

Target = sum (nums)

If target% 2 = = 1:

Return False

Nums.sort ()

Target = target / / 2

Dp = [False] * (target + 1)

Dp [0] = True

For I, n in enumerate (nums):

For j in range (target, n-1,-1):

If dp [j-n] = = True:

Dp [j] = True

Print (dp)

Return dp [- 1]

Thank you for your reading, the above is the content of "how to divide python and subset". After the study of this article, I believe you have a deeper understanding of how to divide python and subset, and the specific use needs to be verified in practice. Here is, the editor will push for you more related knowledge points of the article, welcome to follow!