leetcode416：分割等和子集

题目链接

leetcode

题目描述

给你一个 只包含正整数 的 非空 数组 nums 。请你判断是否可以将这个数组分割成两个子集，使得两个子集的元素和相等。

C++ 代码

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

void printArray(vector<int>& arr) {
    for (int i = 0; i < arr.size(); i ++) {
        if (i != arr.size() - 1) cout << arr[i] << " ";
        else cout << arr[i];
    }
    cout << endl;
}

/*
    对于该问题，先对集合求和得到 sum，然后把问题转化为背包问题。
    给一个容量为 sum/2 的背包和 N 个物品，每个物品的容量为 nums[i]。
    现在需要装物品，是否存在一种方法，可以恰好将背包装满？

    状态定义：
        dp[i][j] 表示前 i 个物品，使用 j 容量的背包是否可以恰好装满。
    状态转移：
        第 i 个物品不装入背包
            dp[i][j] = dp[i-1][j]
        第 i 个物品装入背包
            dp[i][j] = dp[i-1][j-nums[i-1]]

    时间复杂度：O(nm)
        n 表示数组的长度，m 表示容量大小。
    空间复杂度：O(nm)
*/
class Solution {
public:
    bool canPartition(vector<int>& nums) {
        // int sum = 0;
        // for (const int& num : nums) {
        //     sum += num;
        // }
        int sum = accumulate(nums.begin(), nums.end(), 0);
        // 和为奇数时，一定不能划分为两个等和子集
        if (sum % 2 != 0) return false;
        int target = sum / 2;
        
        int n = nums.size();
        vector<vector<bool>> f(n + 1, vector<bool>(target + 1, false));
        for (int i = 0; i <= n; i ++) {
            f[i][0] = true;
        }
        for (int i = 1; i <= n; i ++) {
            for (int j = 1; j <= target; j ++) {
                // 背包容量不足，不能装入该物品
                if (j - nums[i - 1] < 0) f[i][j] = f[i - 1][j];
                // 不装入或装入
                else f[i][j] = f[i - 1][j] || f[i - 1][j - nums[i - 1]];
            }
        }

        return f[n][target];
    }
};

/*
    优化空间

    时间复杂度：O(nm)
        n 表示数组的长度，m 表示容量大小。
    空间复杂度：O(m)
*/
class Solution_1 {
public:
    bool canPartition(vector<int>& nums) {
        int sum = accumulate(nums.begin(), nums.end(), 0);
        // 和为奇数时，一定不能划分为两个等和子集
        if (sum % 2 != 0) return false;
        int target = sum / 2;

        int n = nums.size();
        vector<bool> f(target + 1, false);
        f[0] = true;
        for (int i = 1; i <= n; i ++) {
            for (int j = target; j >= nums[i - 1]; j --) {
                // 不装入或装入
                f[j] = f[j] || f[j - nums[i - 1]];
            }
        }

        return f[target];
    }
};

int main() {
    Solution solution;
    vector<vector<int>> test_case = {
        {1,5,11,5},
        {1,2,3,5}
    };

    for (auto& nums : test_case) {
        cout << "Input: ";
        printArray(nums);
        bool result = solution.canPartition(nums);
        cout << "Output: ";
        cout << (result ? "true" : "false") << endl;
    }

    return 0;
}

Golang 代码

package main

import (
	"fmt"
)

/*
   判断总和是否为偶数：
       如果数组的总和为奇数，或者数组长度小于2，直接返回 false，
       因为无法分割成两个和相等的子集。
   动态规划：
       使用一个布尔数组 dp，其中 dp[j] 表示是否可以找到一个子集，其和为 j。
       初始化 dp[0] = true，因为和为0的情况总是可以达到。
       遍历数组中的每个数字，对于每个数字，从 target 到 num 逆序更新 dp 数组。
   返回结果：
       如果 dp[target] 为 true，说明可以找到一个子集，其和为 target，
       即数组可以被分割成两个和相等的子集。

   时间复杂度：O(n*target)
       遍历数组中的每个数字，对于每个数字，更新 dp 数组的时间复杂度为 O(target)，
       因此总时间复杂度为 O(n*target)，其中 n 是数组的长度。
   空间复杂度：O(target)
       使用了一个大小为 target + 1 的布尔数组 dp，空间复杂度为 O(target)。
*/
// canPartition 判断是否可以将数组分割成两个子集，使得两个子集的元素和相等
func canPartition(nums []int) bool {
	sum := 0
	for _, num := range nums {
		sum += num
	}

	// 如果总和为奇数，或者数组长度小于2，直接返回false
	if sum % 2 != 0 || len(nums) < 2 {
		return false
	}

	target := sum / 2
	dp := make([]bool, target + 1)
	dp[0] = true // 初始化：和为0的情况总是可以达到

	// 动态规划：遍历每个数字，更新dp数组
	for _, num := range nums {
		for j := target; j >= num; j -- {
			dp[j] = dp[j] || dp[j-num]
		}
	}

	return dp[target]
}

func main() {
	// 测试用例
	testCases := []struct {
		nums    []int
		expected bool
	}{
		{
			nums:    []int{1, 5, 11, 5},
			expected: true,
		},
		{
			nums:    []int{1, 2, 3, 5},
			expected: false,
		},
	}

	for i, tc := range testCases {
		result := canPartition(tc.nums)
		fmt.Printf("Test Case %d, Input: nums = %v\n", i+1, tc.nums)
		if result == tc.expected {
			fmt.Printf("Test Case %d, Output: %v, PASS\n", i+1, result)
		} else {
			fmt.Printf("Test Case %d, Output: %v, FAIL (Expected: %v)\n", i+1, result, tc.expected)
		}
	}
}