力扣 416. 分割等和子集 01背包/暴力_力扣剪枝背包

https://leetcode-cn.com/problems/partition-equal-subset-sum/

思路一：$dp$，首先计算数组元素的和，如果为奇数则一定不能满足题意，否则子集的和就等于总和的一半，假设为$half$，那么问题转换成：是否可以从数组中任取一些数字使得它们的和为$half$。$01$背包可解，$dp[i]=1$说明可以组成$i$这个数，否则说明不能组成$i$这个数，那么对于数组中的每个元素$v$都有，$dp[i]=dp[i-v]||dp[i]$，其中$v<=i<=half$。

class Solution {
public:
    bool canPartition(vector<int>& nums) {
        int sum=0;
        for(int i:nums)
            sum+=i;
        if(sum&1)
            return 0;
        if(!sum)
            return 1;
        int half=sum>>1;
        vector<bool> dp(half+1);
        dp[0]=1;
        for(int v:nums){
            for(int i=half;i>=v;i--)
                dp[i]=dp[i]||dp[i-v];
            if(dp[half])
                return 1;
        }
        return 0;
    }
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22

思路二：爆搜+剪枝。

class Solution {
public:
    bool canPartition(vector<int>& nums) {
        int sum=0;
        for(int i:nums)
            sum+=i;
        if(sum&1)
            return 0;
        if(!sum)
            return 1;
        return dfs(sum>>1,0,nums);
    }

    bool dfs(int tar,int idx,vector<int>& nums){
        if(!tar)
            return 1;
        int siz=nums.size();
        for(int i=idx;i<siz;i++){
            if(i>idx&&nums[i]==nums[i-1])
                continue;
            if(tar<nums[i])
                return 0;
            if(dfs(tar-nums[i],i+1,nums))
                return 1;
        }
        return 0;
    }
};
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