leetcode416. 分割等和子集

来源：力扣（LeetCode）

链接：

题目描述

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

示例 1：

输入：nums = [1,5,11,5]

输出：true

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

示例 2：

输入：nums = [1,2,3,5]

输出：false

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

暴力递归的解题技巧:

动态规划其实是对暴力递归的改写,当你对动态规划没有思路时,要先写出暴力递归的尝试,

这道题是典型的 0 -1 背包问题,就是要组成目标和,那我们每到一个位置,都是面临两个选择,选或者不选.分别对两种情况进行递归,最后比较两种递归的情况就可以得到答案了.

还要注意找到base case ,我们代码里注释说明

代码演示:

public boolean canPartition(int[] nums) {

if(nums.length == 1){

return false;

}

//计算数组累加和

int sum = 0;

for(int i = 0 ; i < nums.length;i++){

sum += nums[i];

}

//如果不是偶数没有办法拆分成两个数组和相等

if(sum % 2 != 0){

return false;

}

//能找到拆分方式的数量如果不等于0 ,就是可以拆分

return process(nums,sum / 2,0) != 0;

}

/**

* 暴力递归

* 计算有多少种拆分方式

* target 要组成的目标数字

* index 来到的下标位置

*/

public int process(int[]nums,int target,int index){

//base case 如果来到越界位置,target == 0,前面选择有效,返回1,代表一种有效方案

if(index == nums.length){

return target == 0 ? 1 : 0;

}

//target < 0 说明前面的选择是无效的,返回 0

if(target < 0){

return 0;

}

// target == 0 ,前面选择是合法的,返回1.

if(target == 0){

return 1;

}

//经典背包解法,选和不选两种情况

//不选时 去 index + 1 位置继续做选择

int p1 = process(nums,target,index + 1);

//选时 去 index + 1 位置继续做选择,需要组成的数字还剩target - nums[index]

int p2 = process(nums,target - nums[index],index + 1);

//返回最多的方法数

return Math.max(p1,p2);

}