题目链接
解法一：
bitset
通过bitset存储每(多)种元素相加的情况
class Solution
{
public:bool canPartition(vector<int> &nums){
int sum = 0;bitset<100 * 200 + 1> bits(1);for (auto n : nums){
sum += n;bits |= bits << n;}return !(sum & 1) && bits[sum / 2];}
};
解法二：
DFS
要通过oj首先要对nums进行Larger排序。
class Solution
{
public:bool canPartition(vector<int> &nums){
int sum = accumulate(nums.begin(), nums.end(), 0);sort(nums.begin(), nums.end());return !(sum & 1) && dfs(nums, 0, sum >> 1);}bool dfs(vector<int> &nums, int ind, int target){
if (target <= 0)return target == 0;for (int i = ind; i < nums.size(); i++){
if (target - nums[i] < 0)break;if (dfs(nums, i + 1, target - nums[i]))return true;}return false;}
};
解法三：
DP
class Solution
{
public:bool canPartition(vector<int> &nums){
int sum = 0;for (auto num : nums)sum += num;if (sum & 1)return false;sum /= 2;vector<int> dp(sum + 1, 0);dp[0] = 1;for (auto num : nums)for (int i = sum; i >= num; i--)dp[i] = dp[i] || dp[i - num];return dp[sum];}
};