“This is the second day of my participation in the Gwen Challenge in November. See details: The Last Gwen Challenge in 2021”

1, the title

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].Copy the code

Example 2:

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

Tip:

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

2, train of thought

(Dynamic programming)O(n∗m) O(n * m)O(n∗m)

Given a non-empty array nums[0] containing only positive integers, determine if you can pick numbers from the array such that the sum of these numbers is exactly half of the sum of the elements in the entire array.

Sample:

As shown in the example, nums = [1,5,11,5], the array can be split into [1,5, 5] and [11], so return true.

From the point of view of the question, this problem can be converted to 0-1 backpack problem, how to see? Let’s put it another way:

An array of size n of n items, the array elements and half of the sum as a capacity of a sum / 2 bag, everything can be used only once, the volume of each item is nums [I], whether can solve some items are selected, make these items of the total volume for knapsack capacity, so you can use dynamic programming to solve, Let’s talk about how to do that.

First, if sum is odd, it is impossible to split the array into two equal subsets of elements, so return false. Next we define the state representation and derive the state transition equation.

The state represents: f[I][j] indicates whether the sum of the preceding I numbers is exactly equal to j. So f[I][j] has two states, true or false.

State calculation:

How to determine the value of f[I][j] given that nums[] subscripts start at 1?

To consider the last step, the current nums[I] may or may not be selected:

  • 1, don’t choosenums[i]Then we werei - 1And see if the sum of these numbers is exactly equalj, i.e.,f[i][j] = f[i - 1][j].
  • 2, choosenums[i]In the case that the backpack can fit, then the corresponding backpack capacity will be subtractednums[i] ,f[i][j]State can be accessed fromf[i - 1][j - nums[i]]Transfer over to theta, thetaf[i][j] = f[i - 1][j - nums[i]].

If f[I][j] is true, then f[I] is true. So the state transition equation for f [I] [j] = f [j] [I – 1] | f [I – 1] [j – nums [I]].

Initialization:

F [0][0] = true: we can choose none of the first 0 numbers, so we choose from the first 0 so that the sum of these numbers is exactly equal to 0 and the rest of the states are initialized to false.

Implementation details:

When deriving the state transition equation, we assume that the nums[] array subscripts start at 1, whereas the actual NUMs [] array subscripts start at 0, so we need to subtract 1 from all nums[I] subscripts in the code to be consistent with the language used.

Time complexity analysis: O(n∗m)O(n * m)O(n∗m), where n is the size of the NUMS array and half of the sum of elements in m array.

Spatial complexity analysis: O(n∗m)O(n * m)O(n∗m)

3. Two-dimensional c++ code

class Solution {
public:
    bool canPartition(vector<int>& nums) {
        int n = nums.size(), sum = 0;
        for(int x : nums) sum += x;
        if(sum % 2) return false;
        int m = sum / 2;
        vector<vector<bool>> f(n + 1.vector<bool>(m + 1.false));
        f[0] [0] = true;
        for(int i = 1; i <= n; i++){
            for(int j = 1; j <= m; j++){
                if(j >= nums[i - 1]) f[i][j] = f[i - 1][j - nums[i - 1]] | f[i - 1][j];
                else f[i][j] = f[i - 1][j]; }}returnf[n][m]; }};Copy the code

4. Two-dimensional Java code

class Solution {
    public boolean canPartition(int[] nums) {
        int n = nums.length, sum = 0;
        for(int x : nums) sum += x;
        if(sum % 2! =0) return false;
        int m = sum / 2;
        boolean[][] f = new boolean[n + 1][m + 1];
        f[0] [0] = true;
        for(int i = 1; i <= n; i++){
            for(int j = 1; j <= m; j++){
                if(j >= nums[i - 1]) f[i][j] = f[i - 1][j - nums[i - 1]] || f[i - 1][j];
                else f[i][j] = f[i - 1][j]; }}returnf[n][m]; }}Copy the code

5. One-dimensional optimization

We can find that, in the process of calculation f [I] [j], each row f [j] [I] value with only one line of f [j], [I – 1] so one-dimensional before consider eliminating, the state transition equation as follows: f = f [j] [j] | f [j – nums [I]].

If we continue to consider the second cycle j from small to large, that is:

for (int i = 1; i <= n; i++){ 	             Nums [I] = nums[I - 1]
    for (intj = nums[i]; j <= m; j++){ f[j] = f[i] | f[j - nums[i]]; }}Copy the code

At this point, the state is not equivalent to the two-dimensional state, because when calculating the state of the i-th layer, we enumerate from small to large, j-nums [I] is strictly less than j, then F [j-nums [I]] must be calculated before F [j], so our calculated F [j-nums [I]] is still the i-th layer state. This f [j – nums [I]] is equivalent to f [I] [j – nums [I]], in fact f [j – nums [I]] should be equivalent to the f [I – 1] [j – nums [I]].

In order to solve this problem we just need to changejEnumeration from large to small.

for (int i = 1; i <= n; i++){ 	             Nums [I] = nums[I - 1]
    for (intj = m; j >= nums[i]; j -- ){ f[j] = f[i] | f[j - nums[i]]; }}Copy the code

Because we enumerate j from large to small, and j-nums [I] is strictly less than j, so when we calculate f[j], f[j-nums [I]] has not been updated by the i-layer state, so it only stores the state of the previous layer (i-1 layer), which is equivalent to f[i-1][J-nums [I]].

Spatial complexity analysis: O(n)O(n)O(n)

6. One-dimensional c++ code

class Solution {
public:
    bool canPartition(vector<int>& nums) {
        int n = nums.size(), m = 0;
        for (int x: nums) m += x;
        if (m % 2) return false;
        m /= 2;
        vector<bool> f(m + 1);
        f[0] = true;
        for (int i = 1; i <= n; i++)
            for (int j = m; j >= nums[i - 1]; j -- )
                f[j] = f[j] | f[j - nums[i - 1]].returnf[m]; }};Copy the code

One-dimensional Java code

class Solution {
    public boolean canPartition(int[] nums) {
        int n = nums.length, m = 0;
        for (int x: nums) m += x;
        if (m % 2! =0) return false;
        m /= 2;
        boolean[] f = new boolean[m + 1];
        f[0] = true;
        for (int i = 1; i <= n; i++)
            for (int j = m; j >= nums[i - 1]; j -- )
                f[j] |= f[j - nums[i - 1]].returnf[m]; }}Copy the code
If my article is helpful to you, welcome a key three even!!

Original link: 416. Segmentation and subsets