把nums內的數字分成兩堆,兩堆數字分別的和要相等
Python
動態規劃 : 把加起來的合存到set裡(不會包含重複的資料),不斷的比較是否有合相等的情況,因為set不會包含重複的資料,所以可以一直比較。
class Solution:
def canPartition(self, nums: List[int]) -> bool:
if sum(nums)%2: return 0
st = set([0])
for i in nums:
for j in list(st):
st.add(i + j)
if i + j == sum(nums)//2:
return True
return False
C++
class Solution {
public:
bool canPartition(vector<int>& nums) {
int sum = 0;
for(int i=0;i<nums.size();i++){
sum += nums[i];
}
if(sum%2 != 0){
return false;
}
int target = sum/2;
vector<bool> dp(target+1,false);
dp[0] = true;
for(int i=0;i<nums.size();i++){
for(int j=target;j>=nums[i];j--){
dp[j] = dp[j] || dp[j-nums[i]];
}
}
return dp[target];
}
};