本文共 882 字，大约阅读时间需要 2 分钟。

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

注意:

每个数组中的元素不会超过 100

数组的大小不会超过 200

示例 1:

输入: [1, 5, 11, 5]

输出: true

解释: 数组可以分割成 [1, 5, 5] 和 [11].

示例 2:

输入: [1, 2, 3, 5]

输出: false

解释: 数组不能分割成两个元素和相等的子集.

解题思路：可看成背包问题，属于背包问题里面的0-1背包问题。

class Solution {
       public boolean canPartition(int[] nums) {
           // 动态规划解题 背包问题- 01背包问题 恰好问题	    		    	// 先判断构不构成	    	int sum = 0;	    	for(int num:nums) {
   	    		sum += num;	    	}	    	if(sum%2==1) {
   	    		return false;	    	}	    	// 目标值	    	int target = sum/2;	    	int length = nums.length;	    	// 动态规划	    	boolean[][] dp = new boolean[length+1][target+1];	    	// 初始化	    	for(int i=0;i
   
    =0) {
   	    				// 能放 当前数nums[i-1]	    				dp[i][j] = dp[i-1][j] || dp[i-1][j-nums[i-1]];	    			}else {
   	    				// 没容量	    				dp[i][j] = dp[i-1][j];	    			}	    				    		}	    	}	    	return dp[length][target];    }}
   

转载地址：https://codingchaozhang.blog.csdn.net/article/details/110927427 如侵犯您的版权，请留言回复原文章的地址，我们会给您删除此文章，给您带来不便请您谅解！