da42:背包问题|● 416. 分割等和子集

阿里云国内75折回扣微信号：monov8

阿里云国际，腾讯云国际，低至75折。AWS 93折免费开户实名账号代冲值优惠多多微信号：monov8 飞机：@monov6

题目链接416. 分割等和子集

1.代码

class Solution {
public:
    bool canPartition(vector<int>& nums) {
        int sum = 0;
        for (int i: nums) {
            sum += i;
        }
        if (sum % 2 != 0) return false;
        sum /= 2;
         vector<int>f(sum + 1);
         for (int i = 0; i < nums.size(); i++) {
             for (int j = sum; j >= nums[i]; j--) {
                 f[j] = max(f[j], f[j - nums[i]] + nums[i]);
             }
         }
         if (f[sum] == sum) return true;
         else return false;
    }
};

2.思路

题目的意思是看下可以把这个数组分成两个部分这两部分相加会相等吗如果相等返回false否则返回true,所以只要有一部分数组相加等于nums数组的总和的一半就行了

由此就能把问题转化成从n个数据中找到数据相加等于sum/2的组合可以用回溯法

3.回溯法超时

class Solution {
public:
  int res;
  int flag = 0;
    void backtracking(int sum, vector<int>& nums, int startindex) {
        if (res > sum || flag == 1) return;
        if (res == sum) flag = 1;
        for (int i = startindex; i < nums.size(); i++) {
            res += nums[i];
            backtracking(sum, nums, i + 1);
            res -= nums[i];
        }
   }
    bool canPartition(vector<int>& nums) {
        int sum = 0;
        for (int i: nums) {
            sum += i;
        }     
        if (sum % 2 != 0) return false;  
        sum = sum / 2;
        backtracking(sum, nums, 0);
        if (flag == 1) return true;
        else return false;
    }
};