首页 > 试题广场 >

分割等和子集

[编程题]分割等和子集
  • 热度指数：2072 时间限制：C/C++ 1秒，其他语言2秒 空间限制：C/C++ 256M，其他语言512M
  • 算法知识视频讲解
给定一个只包含正整数的数组 nums ，请问能否把这个数组取出若干个数使得取出的数之和和剩下的数之和相同。

数据范围： ， 数组中的元素满足
示例1

输入

[1,5,11,5]

输出

true

说明

分割为 [1,5,5] 和 [11]
示例2

输入

[1,2,3,5]

输出

false
算法知识视频讲解
添加回答
Java
pein531头像 pein531

暴力递归

首先从左往右进行尝试，写出暴力递归版本。
  1. 当rest<0时，表示本次凑数方案失败；
  2. 当rest=0时，刚好凑齐，本次凑数方案是成功的；
  3. 否则看本轮取哪个数nums[i]，下一轮需要凑rest-nums[i]。 
private boolean recurrent(int[] nums, int depth, int rest) {
    if(rest < 0) return false;
    if(rest == 0) return true;    // base case
    for(int i = depth; i < nums.length; i++){
        if(recurrent(nums, i, rest - nums[i])) return true;
    }
    return false;
}

动态规划 

递归函数有depth和rest两个可变参数，因此本质上是个二维动态规划问题。根据递归的逻辑，就可以改成动态规划版本，递归中的函数调用就是动态规划中从dp数组中取值。
我们可以看到，在计算dp[i][rest]时，需要依赖左边的值，因此动态规划填表的顺序为：从上往下（从下往上也可以，这个顺序无所谓的情况下还可以进行空间压缩的优化）从左往右。 
import java.util.*;


public class Solution {
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     * 
     * @param nums int整型一维数组 
     * @return bool布尔型
     */
    public boolean partition (int[] nums) {
        // write code here
        int sum = 0;
        for(int i = 0; i < nums.length; i++){
            sum += nums[i];
        }
        // 无法均分
        if(sum % 2 != 0){
            return false;
        }
        int target = sum / 2;
        boolean[][] dp = new boolean[nums.length][target + 1];
        for(int i = 0; i < nums.length; i++){
            dp[i][0] = true;    // base case
        }
        for(int i = 0; i < nums.length; i++){
            for(int rest = nums[i]; rest <= target; rest++){
                dp[i][rest] |= dp[i][rest - nums[i]];
            }
        }
        return dp[0][target];
    }
}

编辑于 2021-12-13 21:34:49 回复(0)
空中转体一周半头像 空中转体一周半

暴力递归：和为奇数肯定不能满足。和为偶数再递归查找。

import java.util.*;
public class Solution {
    public boolean partition (int[] nums) {
        int sum = 0;
        for(int i = 0; i < nums.length; ++i) {
            sum += nums[i];
        }
        if(sum % 2 == 1) return false;
        return func(sum / 2, nums, 0, 0);
    }
    public boolean func(int target, int[] nums, int index, int cur) {
        if(cur > target) return false;
        if(cur == target) return true;
        if(index >= nums.length) return false;
        return func(target, nums, index + 1, cur + nums[index]) || func(target, nums, index + 1, cur);
    }
}
发表于 2023-05-11 14:08:33 回复(0)
yuntao229头像 yuntao229 
public:
    bool partition(vector<int>& nums){
        long long sum = 0;
        for(auto num: nums):
            sum += num
        if(sum & 1) return false;
        else return true;
    }
}

发表于 2023-06-26 20:41:36 回复(0)
C++
hiighlight头像 hiighlight
参考0-1背包 
class Solution {
  public:
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     *
     * @param nums int整型vector
     * @return bool布尔型
     */
    bool partition(vector<int>& nums) {
        // write code here
        int sum_nums = 0;
        for (int i : nums) {
            sum_nums += i;
        }
        if (sum_nums % 2 != 0) return false;
        sum_nums = sum_nums / 2;
        vector<int> dp(sum_nums+1, 0);
        for (int i = 0; i < nums.size(); i++) {
            for (int j = sum_nums; j >= 1; j--) {
                if (j - nums[i] >= 0)
                    dp[j] = max(dp[j], dp[j - nums[i]] + nums[i]);
            }
        }
        return dp[sum_nums] == sum_nums;
    }
};


发表于 2022-12-25 23:38:30 回复(0)
Java
古月随风头像 古月随风
最基础的01背包问题 
import java.util.*;


public class Solution {
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     * 
     * @param nums int整型一维数组 
     * @return bool布尔型
     */
    public boolean partition (int[] nums) {
        // write code here
        int sum = 0;
        for(int i = 0; i < nums.length; i++){
            sum += nums[i];
        }
        if(sum % 2 != 0){
            return false;
        }
        int n = sum / 2;
        int[][] dp = new int[nums.length][n + 1];
        for(int i = 1; i < nums.length; i++){
            for(int j = 1; j <= n; j++){
                // 可以放
                if(j >= nums[i]){
                    dp[i][j] = Math.max(dp[i - 1][j], dp[i - 1][j - nums[i]] + nums[i]);
                }else{
                     dp[i][j] = dp[i - 1][j];
                }
            }
        }
        return dp[nums.length - 1][n] == n;
    }
}


发表于 2022-09-14 17:52:15 回复(0)
Python 3
M1ke头像 M1ke 
class Solution:
    def partition(self , nums: List[int]) -> bool:
        '''找重叠子问题'''
        '''不能只靠脑子想'''
        target = sum(nums)
        if target % 2 != 0:
            return False
        dp = [[0 for line in range(target//2 + 1)] for row in range(len(nums))]
        for i in range (1,target//2 + 1):
            if i < nums[0] :
                dp[0][i] = dp[0][i-1]
            else :
                dp[0][i] = nums[0]
        for i in range(1,len(nums)):
            for j in range(1, target//2 + 1):
                if j < nums[i] :
                    dp[i][j] = dp[i-1][j]
                else:
                    dp[i][j] = max(dp[i-1][j], nums[i] + dp[i-1][j-nums[i]])
        if dp[len(nums)-1][target//2] == target//2:
            return True
        else :
            return False


但是会超时 ，没有做优化。

发表于 2022-07-16 21:52:16 回复(0)
提交观点

问题信息

动态规划 数组
难度：
6条回答 1865浏览

热门推荐

通过挑战的用户

查看代码

相关试题

扫一扫，把题目装进口袋

求职之前，先上牛客

扫描二维码，进入QQ群

扫描二维码，关注牛客公众号