LeetCode 416. 分割等和子集（C++、python）

给定一个只包含正整数的非空数组。是否可以将这个数组分割成两个子集，使得两个子集的元素和相等。

注意:

1. 每个数组中的元素不会超过 100
2. 数组的大小不会超过 200

示例 1:

输入: [1, 5, 11, 5]

输出: true

解释: 数组可以分割成 [1, 5, 5] 和 [11].

示例 2:

输入: [1, 2, 3, 5]

输出: false

解释: 数组不能分割成两个元素和相等的子集.

class Solution {
public:
    static bool compare(int a, int b)
    {
        return a>b;
    }
    
    bool dfs(vector<int>& nums, int target, int k)
    {
        if(0==target)
        {
            return true;
        }
        else if(nums[k]>target)
        {
            return false;
        }
        else
        {
           for(int i=k;i<nums.size();i++)
           {
               if(dfs(nums,target-nums[i],i+1))
               {
                   return true;
               }
           }
        }
        return false;
    }
    
    bool canPartition(vector<int>& nums) 
    {
        int sums=accumulate(nums.begin(),nums.end(),0);
        if(1==sums%2)
        {
            return false;
        }
        sort(nums.begin(),nums.end(),compare);
        int target=sums/2;
        return dfs(nums,target,0);       
    }
};

C++

class Solution {
public:
    bool canPartition(vector<int>& nums) 
    {
        int n=nums.size();
        int sum=accumulate(nums.begin(),nums.end(),0);
        if(sum%2)
        {
            return false;
        }
        int target=sum/2;
        vector<vector<int>> tmp(n+1,vector<int>(target+1,0));
        for(int i=1;i<=n;i++)
        {
            if(nums[i-1]>target)
            {
                return false;
            }
            else if(nums[i-1]==target)
            {
                return true;
            }
            else
            {
                for(int j=1;j<=target;j++)
                {
                    if(nums[i-1]==j)
                    {
                        tmp[i][j]=1;
                    }
                    else if(nums[i-1]<j)
                    {
                        tmp[i][j]=tmp[i-1][j] || tmp[i-1][j-nums[i-1]];
                    }
                    else
                    {
                        tmp[i][j]=tmp[i-1][j];
                    }
                }
            }
        }
        return tmp[n][target];
    }
};

python

class Solution:
    def dfs(self, nums, target, k):
        if 0==target:
            return True
        elif k<len(nums) and nums[k]>target:
            return False
        else:
            for i in range(k,len(nums)):
                if self.dfs(nums, target-nums[i], i+1):
                    return True
        return False
    
    def canPartition(self, nums):
        """
        :type nums: List[int]
        :rtype: bool
        """
        sums=sum(nums)
        if sums%2==1:
            return False
        nums=sorted(nums,key=lambda x:-x)
        target=sums//2
        return self.dfs(nums,target,0)
        

最后

以上就是大力玉米为你收集整理的LeetCode 416. 分割等和子集（C++、python）的全部内容，希望文章能够帮你解决LeetCode 416. 分割等和子集（C++、python）所遇到的程序开发问题。

如果觉得靠谱客网站的内容还不错，欢迎将靠谱客网站推荐给程序员好友。