【Leetcode】416. Split equal sum subset

Topic link ： To divide into equal and subsets

Title Description ： To give you one Contains only positive integers Of Non empty Array nums . Please decide whether you can divide this array into two subsets , Make the sum of the elements of the two subsets equal .

Ideas ： Split the array into two equal sum subsets .

that ：

1） The sum of array elements must be even , And the array length must be greater than 1. And the maximum value of the array cannot be greater than half of the sum of the array

2） The question turned to ： Whether there are several elements in the array , The sum is half the sum of all the elements of the array . That is to find the sum of several elements as target.

The original idea is ： Sort elements , Then use the method of backtracking , Passed 100 Multiple samples . A few sample errors remain , After repeated thinking and trying to find the method of backtracking is not right .

So I read the solution , See light suddenly .

0-1 knapsack problem ：

Yes n Two objects and a backpack , take n Several of the objects are put into the backpack . Each object can only be placed 1 Time , That is to say, every object is either placed or , Or not .

The corresponding question is ,n Select several of the objects and put them into one with the size of target The backpack , Can it be just full .

Define an array dp[n][target+1],dp[i][j] Indicates whether or not [0,i] Select several of the numbers so that the sum is just j. Final dp[n-1][target] It's what you want . Adopted Dynamic programming Thought .

Because every object can be put or not , So there is a classified discussion , The state transition equation is obtained .

If j==nums[i], Then only the i One object is enough , namely dp[i][j]=true,

If j<nums[i], Is the first i Objects cannot be placed in a size of j In my backpack , Only in the past [0,i-1] Take from objects , namely dp[i][j]=dp[i-1][j].

If j>nums[i], So the first i Objects can be placed in a size of j In my backpack , You can also choose not to put . namely dp[i][j]=dp[i-1][j] || dp[i-1][j-nums[i]]

The boundary condition is ： The first column is full of false, The first line is just nums[0] The corresponding value is true.

js The code is as follows ：

var canPartition = function (nums) {
    const length = nums.length;
    if (length == 1)
        return false;
    let sum = 0;
    let max=0;
    for (let num of nums) {
        sum += num;
        max=Math.max(max,num);
    }
    const target=sum/2;
    if (sum % 2 == 1)
        return false;
    if(max>target)
        return false;
   
    let dp=new Array(length);
    for(let i=0;i<length;i++){
        dp[i]=new Array(target+1).fill(false);
    }
    dp[0][nums[0]]=true;
    for(let i=1;i<length;i++){
        for(let j=1;j<=target;j++){
            if(j===nums[i])
                dp[i][j]=true;
            else if(j<nums[i])
                dp[i][j]=dp[i-1][j];
            else
                dp[i][j]=dp[i-1][j] || dp[i-1][j-nums[i]];
        }
    }
    return dp[length-1][target];
};

Time complexity ：O(n target), Spatial complexity O(n target)

From the state transfer equation we can see that ,dp Each row of the is only related to data of the previous row , So there is no need to maintain a two-dimensional array , You can use one-dimensional arrays .

namely dp[j]=dp[j] || dp[j-nums[i]], here dp[j] and dp[j-nums[i]] It should be the data before updating , So in the j When traversing , It should be from the back to the front , This ensures that dp[j-nums[i]] It has not been updated . If from the past to the future , Then we will use dp[j-nums[i]] It's the updated , Cause the result to go wrong . If you traverse from front to back , Also can put the dp[j-nums[i]] Put it in storage .

js The code is as follows ：

var canPartition = function (nums) {
    const length = nums.length;
    if (length == 1)
        return false;
    let sum = 0;
    let max = 0;
    for (let num of nums) {
        sum += num;
        max = Math.max(max, num);
    }
    const target = sum / 2;
    if (sum % 2 == 1)
        return false;
    if (max > target)
        return false;
    //  One dimensional arrays can also 
    let dp = new Array(target + 1).fill(false);
    dp[nums[0]] = true;
    dp[0] = true;
    for (let i = 1; i < length; i++) {
        // debugger
        for (let j = target; j >= nums[i]; j--) {
            dp[j] = dp[j] || dp[j - nums[i]];
        }
    }
    return dp[target];
};

Time complexity ：O(n target), Spatial complexity O(target)