01 Backpack interview questions series （ One ）

Title Description —— To divide into equal and subsets

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 .

Example 1：

 Input ：nums = [1,5,11,5]
 Output ：true
 explain ： Arrays can be divided into  [1, 5, 5]  and  [11] .

Example 2：

 Input ：nums = [1,2,3,5]
 Output ：false
 explain ： An array cannot be divided into two elements and equal subsets .

01 Knapsack dynamic programming solution

At first glance, the above problem seems to be a subset partition problem , We may base on the data nums Get all its subsets , Then add up all yourself to see if there is a sum of a subset of data nums Half of the sum of all data in the array , In fact, we can do this , We will discuss this method in detail later .

Then we change how to use 01 knapsack To solve this problem ？ Let's first review 01 knapsack What problems have been solved ：

Yes $N$ Items and a capacity are $V$ The backpack . Each item can only be used once . The first $i$ The volume of the item is $v_i$, The value is $w_i$. Find out which items to pack in your backpack , The total volume of these items can not exceed the capacity of the backpack , And the total value is the greatest .

01 knapsack It is a backpack with a given capacity , See the maximum value he can put into the item . So how can we turn the above problems into 01 knapsack Well ？

We can do this , take nums The value in the array becomes the value and volume of the item , for instance nums = [1, 2, 3], We can divide it into three items , The volume and value of these three items are 1 and 1、2 and 2 and 3 and 3, The capacity of our backpack is V = (1 + 2 + 3) / 2. We will nums Half of the sum of all the data in the array is the capacity of the backpack ,nums The value in it represents the value and volume of each item , And the value and volume are equal , If we can just fill our backpacks , There is a combination of objects whose sum is nums Half of the sum of the data in the array .

So how do we judge that the backpack is just full ？ We know that the knapsack problem is solved only when the knapsack capacity is certain , What is the greatest value we can get , Therefore, it seems impossible to judge whether the backpack is full ！ But in the process of above transformation, the volume and value of goods are equal , Because we can judge according to the maximum value we get , If we finally get the income equal to the capacity of the backpack , That means the backpack is full , That is, there is a combination of items, and the maximum value we can obtain is equal to half of the sum of the data in the array . Because the value and volume of the goods are equal , Therefore, filling the backpack is equivalent to getting the maximum value .

Therefore, according to the above analysis , If we want to use it 01 Backpack to solve this problem , We can set the backpack capacity to nums Half of the sum of data in the array , The number of items is the length of the array , The value and volume of the item are the values of the corresponding positions in the array , Then proceed 01 Knapsack solution can .

If you don't know much about 01 Backpacks , You can look at This article , This article mainly from 0 It started to introduce 01 knapsack problem , From two-dimensional array to rolling array to one-dimensional array , The optimization process progresses layer by layer , Take you from principle to actual combat to fully master 01 knapsack problem .

So our code is as follows （ One dimensional array optimization ）：

class Solution {
    
  public boolean canPartition(int[] nums) {
    
    int sum = 0;
    for (int num : nums) {
    
      sum += num;
    }
    if ((sum & 1) == 1) return false;
    int t = sum / 2;
    int[] dp = new int[t + 1];
    for (int i = 0; i < nums.length; i++) {
    
      for (int j = t; j >= nums[i]; j--) {
    
        dp[j] = Math.max(dp[j], dp[j - nums[i]] + nums[i]);
      }
    }
    return dp[t] == t;
  }
}

Subset partition solution

We know that the number of subsets of any set is $2^n$, among $n$ Represents the number of data in the set , Let's say a collection $1,2$ Like a subset （4 individual ）：
$$\{An\; empty\; set\},\{1\},\{2\},\{1,2\}$$
Let's think about $2^n$ How to calculate it ！ When we generate subsets, we can choose or not choose each data , This actually becomes a permutation and combination problem . In the example above 1 No choice （2）,2 No choice （2）, Therefore, the total number of sets is 4, So if there is n A set of data, then its own number is equal to ：
$$2\times 2\times 2\cdots =2^n$$
The division of this selection is shown in the following figure ：

And we use programs to calculate a subset of a set is actually a backtracking problem , The code for dividing subsets and subsets is as follows ：

public class Solution {
    
    private int target;
    public boolean canPartition(int[] nums) {
    

        int sum = 0;
        for (int num : nums) {
    
            sum += num;
        }
        if ((sum & 1) == 1 ) return false;
        //  Our ultimate goal is to find our own sum equal to this number 
        target = sum / 2;
        return backTrace(-1, 0, nums);
    }

    /** * @param curIndex  Indicates the position of the currently traversed array  * @param curSum  The sum of all data in the current collection  * @param nums  Array to be traversed  * @return */
    public boolean backTrace(int curIndex, int curSum, int[] nums) {
    
        if (curSum == target) return true;
        //  Here is the pruning operation   If the current sum is greater than the target value or 
        //  When the index of traversal exceeds the length of the array, it returns  false  Express 
        //  This branch did not find a set , The sum of the data in the set is equal to  target
        else if (curSum > target || curIndex >= nums.length - 1) return false;
        //  Select a data 
        curSum += nums[curIndex + 1];
        if (backTrace(curIndex + 1, curSum, nums))
            return true;
        //  Do not select a data   Corresponding to this backtracking operation 
        curSum -= nums[curIndex + 1];
        return backTrace(curIndex + 1, curSum, nums);
    }
}

We know that the time complexity of dynamic programming is $O(n^2)$, The time complexity of this method of generating subsets is $O(2^n)$. So if you LeetCode Submitting this code on will timeout .

summary

This article mainly introduces To divide into equal and subsets This topic , This problem can be solved by either dynamic programming or backtracking , But the time complexity of backtracking method is too high . The method of using dynamic programming solution is still relatively abstract , You may need to spend time thinking about it , I hope you can get something , I am a LeHung, See you next time ！！！（ Remember give the thumbs-up Collection ！）

More wonderful content collections can be accessed to the project ：https://github.com/Chang-LeHung/CSCore

Official account ： Worthless research monk , Learn more about computers （Java、Python、 Fundamentals of computer system 、 Algorithm and data structure ） knowledge .