解题思路

这是一个01背包问题的变体：

  1. 问题分析：

    • 目标：找到一些数，使其和等于剩余数之和
    • 等价于：找到一些数，使其和等于总和的一半
    • 因为：如果一部分和为 ，那么剩余部分也为

  2. 解题步骤：

    • 先求出数组总和
    • 如果 是奇数，直接返回 false
    • 问题转化为：能否从数组中选择一些数，使其和为
    • 使用01背包求解

  3. 动态规划设计：

    • 状态定义： 表示是否能凑出和为
    • 初始化：，其他为
    • 状态转移：

代码

#include <iostream>
#include <vector>
#include <numeric>
using namespace std;

bool canPartition(vector<int>& nums) {
    int sum = accumulate(nums.begin(), nums.end(), 0);
    
    // 如果总和为奇数，无法平分
    if(sum % 2 != 0) return false;
    
    int target = sum / 2;
    vector<bool> dp(target + 1, false);
    dp[0] = true;
    
    // 对每个数进行01背包
    for(int num : nums) {
        // 从后向前遍历
        for(int j = target; j >= num; j--) {
            dp[j] = dp[j] || dp[j - num];
        }
    }
    
    return dp[target];
}

int main() {
    int n;
    cin >> n;
    vector<int> nums(n);
    for(int i = 0; i < n; i++) {
        cin >> nums[i];
    }
    cout << (canPartition(nums) ? "true" : "false") << endl;
    return 0;
}

import java.util.*;

public class Main {
    public static boolean canPartition(int[] nums) {
        int sum = 0;
        for(int num : nums) sum += num;
        
        // 如果总和为奇数，无法平分
        if(sum % 2 != 0) return false;
        
        int target = sum / 2;
        boolean[] dp = new boolean[target + 1];
        dp[0] = true;
        
        // 对每个数进行01背包
        for(int num : nums) {
            // 从后向前遍历
            for(int j = target; j >= num; j--) {
                dp[j] = dp[j] || dp[j - num];
            }
        }
        
        return dp[target];
    }
    
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();
        int[] nums = new int[n];
        for(int i = 0; i < n; i++) {
            nums[i] = sc.nextInt();
        }
        System.out.println(canPartition(nums) ? "true" : "false");
        sc.close();
    }
}

def can_partition(nums: list) -> bool:
    total = sum(nums)
    
    # 如果总和为奇数，无法平分
    if total % 2 != 0:
        return False
    
    target = total // 2
    dp = [False] * (target + 1)
    dp[0] = True
    
    # 对每个数进行01背包
    for num in nums:
        # 从后向前遍历
        for j in range(target, num - 1, -1):
            dp[j] = dp[j] or dp[j - num]
    
    return dp[target]

if __name__ == "__main__":
    n = int(input())
    nums = list(map(int, input().split()))
    print("true" if can_partition(nums) else "false")

算法及复杂度

  • 算法：动态规划（01背包）
  • 时间复杂度：，其中 是数组长度， 是总和的一半
  • 空间复杂度：，使用一维 数组