【leetcode】 416. Partition Equal Subset Sum

发表于

描述
给定一个int类数据集合，你需要判断这两个数据集合能否分成两个相等的部分，也就是说一部分等于总和的一般
我想了一个算法，枚举，O(2^N)，(*￣ω￣)

我的解法

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
class Solution {
public:
    bool canPartition(vector<int>& nums) {
        int sumval = accumulate(nums.begin(), nums.end(), 0);
        if (sumval % 2 == 1) { return false; }
        int midval = sumval / 2;
        int nNums = nums.size();

        for (auto num : nums) {
            if (num > midval) {
                return false;
            }
        }

        for (int i = 0; i < pow(2, nNums); i++) {
            int sumNums = 0;
            for (int j = 0; j < nNums; j++) {
                if (i >> nNums - 1 - j & 1) { sumNums += nums[j]; }
                if (sumNums == midval) { return true; }
                else if (sumNums > midval) { break; }
            }
        }
        return false;
    }
};

这个是我写的一个递归的版本，好像没有什么效果。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
public:
    bool canPartition(vector<int>& nums) {
        int sumval = accumulate(nums.begin(), nums.end(), 0);
        if (sumval % 2 == 1) { return false; }
        int midval = sumval / 2;
        int nNums = nums.size();

        for (auto num : nums) {
            if (num > midval) {
                return false;
            }
        }

        if(findn(nNums-1,midval,nums)==ture){return true;}
        return false;
    }

    bool findn(int iNum, int midval, vector<int>& nums) {
    if (midval == 0) {
        return true;
    }
    if (midval < 0) {
        return false;
    }
    if (iNum == 0 && midval == nums[0]) {
        return true;
    }
    if (iNum == 0 && midval != nums[0]) {
        return false;
    }
    return findn(iNum - 1, midval - nums[iNum], nums) || findn(iNum - 1, midval, nums);
}
};

更好的解法

参考链接
基于贪心的dp算法，强大。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
class Solution {
public:
    bool canPartition(vector<int>& nums) {
        int sum = accumulate(nums.begin(), nums.end(), 0);
        if (sum & 1) { return false; }
        int half = sum / 2;

        //sort it from big to small then you can use dp
        //it is quickly,because it's greedy
        sort(nums.begin(), nums.end(), greater<int>());
        return canPartitionRecrusion(nums, half, 0);
    }

    bool canPartitionRecrusion(vector<int>& nums,int half,int index) {
        for (int i = index; i < nums.size(); i++) {
            int h = half - nums[i];
            if (h == 0) { return true; }
            if (h <0) { return false; }
            if (canPartitionRecrusion(nums, h, i + 1) == true) { return true; };
        }

        return false;
    }

};

另一种解法

代码很精炼，有点难理解，下标即总和，厉害。
实际上利用了一个数组模拟了所有的加法总和情况，太精巧了。Ψ(￣∀￣)Ψ

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
class Solution {
public:
    bool canPartition(vector<int>& nums) {
        int sum = std::accumulate(nums.begin(), nums.end(), 0);
        if (sum%2!=0) return false;
        vector<int> dp(sum+1, 0);
        dp[0] = 1;
        for (const int num: nums){
            for (int i= sum; i>=0; --i){
                if (dp[i]) dp[i+num]= true;
            }
            if (dp[sum/2]) return true;
        }return false;
    }
};

参考资料
原题链接