分割等和子集

题意

判断数组能否分成两个和相等的子集。

思路

若总和为奇数，不可能。否则目标为 sum/2，转化为 0/1 背包：从 nums 中选若干数，和恰好为 target。dp[i] 表示和 i 是否可达，倒序更新避免重复使用同一元素。

代码

cpp

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#include <bits/stdc++.h>
using namespace std;

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

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int n;
    cin >> n;
    vector<int> a(n);
    for (int &x : a)
        cin >> x;
    cout << Solution().canPartition(a) << '\n';
    return 0;
}

python

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#!/usr/bin/env python3
from typing import List


class Solution:
    def canPartition(self, nums: List[int]) -> bool:
        s = sum(nums)
        if s & 1:
            return False
        target = s // 2
        dp = [False] * (target + 1)
        dp[0] = True
        for x in nums:
            for i in range(target, x - 1, -1):
                dp[i] = dp[i] or dp[i - x]
        return dp[target]


def main():
    n = int(input())
    a = list(map(int, input().split()))
    print(Solution().canPartition(a))


if __name__ == "__main__":
    main()

复杂度

时间复杂度： $O(n \cdot \text{target})$ 。
空间复杂度： $O(\text{target})$ 。

总结

分割等和子集是 0/1 背包的判定版本。倒序更新是关键：正序更新会导致同一元素被多次选取。

目录

题意

思路

代码

复杂度

总结