力扣-416.分割等和子集

题目描述

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

class Solution {public boolean canPartition(int[] nums) {int sum = 0;for(int i = 0; i < nums.length; i++){sum += nums[i];}if(sum % 2 == 1)return false;int target = sum / 2;int[] dp = new int[target+1];//dp数组的含义是大小为j的背包最多可以装多少for(int i = 0; i < nums.length; i++){//先遍历物品，再遍历背包for(int j = target; j >=1; j--){//从后往前遍历，保证每个物品只用一次if(j-nums[i]>=0)dp[j] = Math.max(dp[j], dp[j-nums[i]]+nums[i]);}}return dp[target]==target;}
}

小结：刚开始考虑回溯做这道题如下，非常直观而且容易想到，结果超时了

class Solution {int sum = 0;boolean judge = false;void backtracking(int[] nums, int target, int startIndex){if(sum == target){judge = true;return;}for(int i = startIndex; i < nums.length; i++){sum += nums[i];backtracking(nums, target, i+1);sum -= nums[i];}}public boolean canPartition(int[] nums) {int sum = 0;for(int i = 0;i<nums.length;i++){sum+=nums[i];}if(sum%2==1){return false;}int target = sum/2;backtracking(nums,target,0);return judge;}
}