C++ 解法, 执行用时: 3ms, 内存消耗: 412KB, 提交时间: 2022-05-26

class Solution {
public:
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     * 
     * @param nums int整型vector 
     * @return bool布尔型
     */
    bool backtracking(vector<int>& nums, int target, int startindex, vector<bool>& used) {
        if (target == 0)    return true;
        if (target < 0)    return false;
        for (int i = startindex; i < nums.size(); ++i) {
            if (used[i])    continue;
            used[i] = true;
            if (backtracking(nums, target - nums[i], startindex+1, used))    return true;
            used[i] = false;
        }
        return false;
    }
    bool partition(vector<int>& nums) {
        // write code here
        int sum = 0;
        for (int n : nums) {
            sum += n;
        }
        if (sum % 2 != 0)    return false;
        int target = sum / 2;
        vector<bool> used(nums.size(), false);
        sort(nums.begin(), nums.end());
        return backtracking(nums, target, 0, used);
    }
};

C++ 解法, 执行用时: 3ms, 内存消耗: 416KB, 提交时间: 2022-07-26

#include <bits/stdc++.h>

class Solution {
public:

bool combinate(const std::vector<int> &nums, int target, std::vector<int> &visited, int index)
{
  if (target == 0)
  {
    return true;
  }

  if (target < 0)
  {
    return false;
  }

  for (int i = index; i < nums.size(); ++i)
  {
    if (visited[i] == 1)
    {
      continue;
    }

    visited[i] = 1;
    if (combinate(nums, target - nums[i], visited, i + 1))
    {
      return true;
    }
    visited[i] = 0;
  }
  return false;
}

bool partition(vector<int> &nums)
{
  int s = std::accumulate(nums.begin(), nums.end(), 0);
  if (s % 2 != 0)
  {
    return false;
  }
  std::sort(nums.begin(), nums.end());
  int target = s / 2; // 实际上就是在nums中是否存在k个数的和为target
  std::vector<int> v(nums.size(), 0);
  return combinate(nums, target, v, 0);
}
};

C++ 解法, 执行用时: 3ms, 内存消耗: 432KB, 提交时间: 2022-06-03

class Solution {
public:
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     * 
     * @param nums int整型vector 
     * @return bool布尔型
     */
    bool partition(vector<int>& nums) 
    {
        int sum=0;
        vector<int>dp(10001,0);
        for(int i=0;i<nums.size();i++)
        {
            sum+=nums[i];
        }
        if(sum%2==1)return false;
        sum/=2;
        auto  first=nums.begin();
        int i=nums.size()-1;
        while(i>=0 && sum>0) {
            sum-=nums[i];
            auto iter=upper_bound(first, first+i, sum);
            i=iter-first-1;
        }
         
        return sum==0;
        // write code here
    }
};

C++ 解法, 执行用时: 3ms, 内存消耗: 520KB, 提交时间: 2022-07-10

#include<numeric>
class Solution {
public:
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     * 
     * @param nums int整型vector 
     * @return bool布尔型
     */
    bool partition(vector<int>& nums) {
        // write code here
        int sum = accumulate(nums.begin(),nums.end(),0);
        if(sum % 2!=0)
            return false;
        int half = sum/2;
        
        vector<int> half_dig(half+1,0);
        half_dig[0] = 1;
        for(int j = 0; j < nums.size(); ++j){
            for(int i  = 0; i <= half; ++i){
                if(half_dig[i] == 1 && i+nums[j]<=half){
                    if(half_dig[half] == 1)
                        return true;
                    half_dig[i+nums[j]] = 1;
                    
                }
            }
        }
        return false;
        
    }
};

C++ 解法, 执行用时: 3ms, 内存消耗: 536KB, 提交时间: 2021-12-11

class Solution {
public:
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     * 
     * @param nums int整型vector 
     * @return bool布尔型
     */
    bool partition(vector<int>& nums) {
        int sum=0;
        for(int val : nums)
            sum+=val;
         
        if((sum & 1)!=0) return false;
        
        sort(nums.begin(), nums.end());
        
        int i=nums.size()-1;
        sum/=2;
        auto first=nums.begin();
        while(i>=0 && sum>0) {
            sum-=nums[i];
            auto iter=upper_bound(first, first+i, sum);
            i=iter-first-1;
        }
        
        return sum==0;
    }
};