Topic describes

You are given a non-empty array nums containing only positive integers. Determine if you can split this array into two subsets so that the sum of the elements in the two subsets is equal.

 

Example 1:

Input: nums = [1,5,11,5] Output: true Explanation: Arrays can be split into [1,5, 5] and [11].

Example 2:

Input: nums = [1,2,3,5] output: false explanation: an array cannot be split into two elements and equal subsets.

Tip:

1 <= nums.length <= 200 1 <= nums[i] <= 100

Source: LeetCode link: leetcode-cn.com/problems/pa… Copyright belongs to the Collar buckle network. Commercial reprint please contact official authorization, non-commercial reprint please indicate the source.

Their thinking

01 Knapsack 🎒 problem – Existential solution

01 knapsack 🎒

答 案 :

  • Can the array elements be split into two subsets, numsA numsB and res= numsa-numsb; res===0;

  • Sum =numsA+numsB; Is there a subset whose sum is weight=sum/2?

Four steps for dynamic programming:

  • Determine the meaning of dp array:
    • Whether there is a subset whose sum is j; false/true
  • Determine the recursion formula:
    • It is assumed that the subset plus num[I], and equal to j, satisfies the assumption as long as dp[j-nums [I]] exists
    • Assume that the subset does not add num[I] and that the sum is equal to j, satisfying the assumption as long as dp[j] exists
    • So the recursive formula is:
    • dp[j]=dp[j]||dp[j-nums[i]]
  • * dp[0]=true; You don’t need any elements, the topic is not an empty array, just a basis for recursion;
  • Determine the traversal order
    • 01 Backpack 🎒 questions:
    • 01 Knapsack must be an outer for loop traversal item, inner for loop traversal knapsack capacity and traversal from back to front!

code

/ * * *@param {number[]} nums
 * @return {boolean}* /
var canPartition = function(nums) {

   let sum=0;
   for(let item of nums){
       sum+=item;
   } 
   if(sum&1= = =1) {// odd numbers cannot be divided equally;
       return false;
   }
   let weight=Math.floor(sum/2);

   let dp=new Array(weight+1).fill(false);
    dp[0] =true;
   for(let i=0; i<nums.length; i++){for(letj=weight; j>=nums[i]; j--){ dp[j]=dp[j]||dp[j-nums[i]] } }// end of for ;
   console.log(dp,dp[weight]);
   return dp[weight]

};
Copy the code

Full backpack 🎒 problem

【 Review old and learn new 】322. ChangeAnimation demonstration – minimum solution of complete knapsack problem – Implementation of dynamic programming

【 Review old and learn new 】518. Change IICombinatorial solution of complete knapsack problem – Implementation of dynamic programming

【 Review old and learn new 】377. Sum of combinations ⅳPermutation solution of complete knapsack problem – Implementation of dynamic programming

01 Backpack 🎒 problem

【 Review old and learn new 】474. One and zero01 knapsack 🎒 problem maximum solution – dynamic programming implementation

【 Review old and learn new 】494. The target andExpression into 01 knapsack 🎒 problem – dynamic programming implementation

【 Review old and learn new 】1049. The weight of the last stone IIMinimum weight conversion to 01 knapsack 🎒 problem maximum solution – dynamic programming implementation