分割等和子集

题目要求

这个问题是一个典型的判断型问题，要求我们确定一个只包含正整数的非空数组是否可以被分割成两个和相等的子集。这个问题实际上是一个背包问题的变种，可以通过动态规划来解决。

解题思路

要解决这个问题，我们可以采用动态规划的方法。以下是解题的步骤：

计算总和：首先，我们需要计算数组 nums 的总和 sum。如果 sum 是奇数，那么不可能将数组分割成两个和相等的子集，因为两个整数和相等意味着每个子集的和必须是总和的一半，即 sum / 2，而奇数不能被平均分割成两个相等的整数。
初始化动态规划数组：如果 sum 是偶数，我们可以继续解题。我们创建一个布尔类型的动态规划数组 dp，大小为 sum / 2 + 1，用于存储子集和为索引值的可能性。dp[0] 是 true，因为不选择任何元素时，任何数组都可以形成和为 0 的子集。
填充动态规划数组：接下来，我们遍历数组 nums，对于每个元素 num 和每个可能的子集和 i（从 sum / 2 到 num），我们更新 dp[i]。如果 dp[i] 之前是 false，我们检查 dp[i - num] 是否为 true，如果是，那么我们可以通过添加 num 到和为 i - num 的子集来形成和为 i 的子集，因此我们将 dp[i] 设置为 true。
检查结果：最后，我们检查 dp[sum / 2] 是否为 true。如果是，那么我们可以将数组分割成两个和相等的子集；如果不是，那么不可能分割。

这个动态规划解法的时间复杂度是 O(n * sum/2)，其中 n 是数组 nums 的长度，空间复杂度是 O(sum/2)，因为我们只需要一个一维数组来存储状态。

Golang 版本

package main

import "fmt"

func canPartition(nums []int) bool {
    total := 0
    for _, num := range nums {
        total += num
    }
    // 如果总和是奇数，则不能平分
    if total%2 != 0 {
        return false
    }

    target := total / 2
    dp := make([]bool, target+1)
    dp[0] = true

    for _, num := range nums {
        for i := target; i >= num; i-- {
            dp[i] = dp[i] || dp[i-num]
        }
    }

    return dp[target]
}

func main() {
    nums := []int{1, 5, 11, 5}
    fmt.Println(canPartition(nums)) // 输出: true
}

这段代码定义了一个 canPartition 函数，它接受一个整数数组 nums 作为输入，并返回一个布尔值，表示是否可以将数组分割成两个和相等的子集。主函数 main 中给出了一个示例数组，并打印出调用 canPartition 函数的结果。

C++版本

#include <iostream>
#include <vector>

using namespace std;

bool canPartition(vector<int>& nums) {
    int sum = 0;
    for (int num : nums) {
        sum += num;
    }
    if (sum % 2 != 0) return false; // 如果总和是奇数，则不能平分

    int target = sum / 2;
    vector<bool> dp(target + 1, false);
    dp[0] = true;

    for (int num : nums) {
        for (int i = target; i >= num; --i) {
            dp[i] = dp[i] || dp[i - num];
        }
    }

    return dp[target];
}

int main() {
    vector<int> nums = {1, 5, 11, 5};
    cout << (canPartition(nums) ? "true" : "false") << endl; // 输出: true
    return 0;
}

这段代码定义了一个 canPartition 函数，它接受一个整数向量 nums 作为输入，并返回一个布尔值，表示是否可以将数组分割成两个和相等的子集。main 函数中给出了一个示例向量，并打印出调用 canPartition 函数的结果。

Python 版本

def can_partition(nums):
    total_sum = sum(nums)
    # 如果总和是奇数，则不能平分
    if total_sum % 2 != 0:
        return False

    target = total_sum // 2
    dp = [False] * (target + 1)
    dp[0] = True

    for num in nums:
        for i in range(target, num - 1, -1):
            dp[i] = dp[i] or dp[i - num]

    return dp[target]

# 示例
nums = [1, 5, 11, 5]
print(can_partition(nums))  # 输出: True

Java 版本

public class Solution {

    public 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;

        for (int num : nums) {
            for (int i = target; i >= num; i--) {
                dp[i] = dp[i] || dp[i - num];
            }
        }

        return dp[target];
    }

    public static void main(String[] args) {
        Solution solution = new Solution();
        int[] nums = {1, 5, 11, 5};
        System.out.println(solution.canPartition(nums)); // 输出: true
    }
}

这段代码定义了一个 Solution 类，其中包含一个 canPartition 方法，该方法接受一个整数数组 nums 作为输入，并返回一个布尔值，表示是否可以将数组分割成两个和相等的子集。main 方法中给出了一个示例数组，并打印出调用 canPartition 方法的结果。

Rust 版本

fn can_partition(nums: Vec<i32>) -> bool {
    let total_sum: i32 = nums.iter().sum();
    // 如果总和是奇数，则不能平分
    if total_sum % 2 != 0 {
        return false;
    }

    let target = total_sum / 2;
    let mut dp = vec![false; (target + 1) as usize];
    dp[0] = true;

    for &num in &nums {
        for i in (num..=target).rev() {
            if i >= num {
                dp[i as usize] = dp[i as usize] || dp[(i - num) as usize];
            }
        }
    }

    dp[target as usize]
}

fn main() {
    let nums = vec![1, 5, 11, 5];
    println!("{}", can_partition(nums)); // 输出: true
}

这段代码定义了一个 can_partition 函数，它接受一个整数向量 nums 作为输入，并返回一个布尔值，表示是否可以将数组分割成两个和相等的子集。main 函数中给出了一个示例向量，并打印出调用 can_partition 函数的结果。

总结

上述问题是一个经典的动态规划问题，目标是确定一个只包含正整数的非空数组是否可以被分割成两个和相等的子集。解决方案遵循以下步骤：

计算数组总和：首先计算给定数组的总和。如果总和是奇数，直接返回 false，因为奇数不能被平分成两个相等的整数。
确定目标子集和：将总和除以 2 得到目标子集和。
初始化动态规划数组：创建一个布尔类型的动态规划数组 dp，其长度为目标子集和加一。这个数组用于存储从 0 到目标子集和的每个值是否可以通过数组中的数字组合得到。dp[0] 初始化为 true，因为总是可以组合出子集和为 0。
填充动态规划数组：遍历数组中的每个数字，然后逆序遍历从该数字到目标子集和的每个值。如果 dp[i] 在添加当前数字之前还不是 true，检查 dp[i - num] 是否为 true。如果是，将 dp[i] 设置为 true。
检查是否可以分割：最后，检查 dp[target] 是否为 true。如果是，说明可以将数组分割成两个和相等的子集。

这种方法在不同的编程语言中实现时，核心算法保持不变，只是语法和一些数据结构的使用有所差异。在所有给出的代码示例中，时间复杂度都是 O(n * sum/2)，其中 n 是数组 nums 的长度，空间复杂度是 O(sum/2)。这是因为我们只需要一个一维数组来存储从 0 到目标子集和的可能性。

hot-100