1 回溯法

class Solution { public: bool backtrack(vector<int>& nums, int start, int target) { if (target <= 0) return target == 0; for (int i = start; i < nums.size(); i++) if (backtrack(nums, i + 1, target - nums[i])) return true; return false; } bool canPartition(vector<int>& nums) { int sum = accumulate(nums.begin(), nums.end(), 0); return !(sum & 1) && backtrack(nums, 0, sum >> 1); } };

2 动态规划

class Solution { public: bool canPartition(vector<int>& nums) { int sum = accumulate(nums.begin(), nums.end(), 0); if(sum&1) return false; vector<int> dp(sum+1,0); dp[0]=1; for(auto num: nums){ for(int i=sum; i>=0; i--){ if(dp[i]) dp[i+num]=1; } if(dp[sum>>1]) return true; } return false; } };

3 位运算

bool canPartition(vector<int>& nums) { bitset<5001> bits(1); int sum = accumulate(nums.begin(), nums.end(), 0); for (auto n : nums) bits |= bits << n; return !(sum & 1) && bits[sum >> 1]; }