无锡网站开发平台_最好用的手机编程软件_建立网站的基本步骤_项目宣传推广方案

Problem

Given an integer array nums, return true if you can partition the array into two subsets such that the sum of the elements in both subsets is equal or false otherwise.

Algorithm

Dynamics Programming (DP). Sum all the number and find if there are subset that the sum can get the half of the total sum.
Use DP to find if the value can be formed.

Code

class Solution:def canPartition(self, nums: List[int]) -> bool:sum_n = 0for num in nums:sum_n += numif sum_n % 2 == 1:return Falsehalf = sum_n // 2visit = [0] * (half + 1)visit[0] = 1for num in nums:for v in range(half, num-1, -1):if visit[v - num]:visit[v] = 1return  visit[half] == 1