Technology Sharing

한어Русский языкEnglishFrançaisIndonesianSanskrit日本語DeutschPortuguêsΕλληνικάespañolItalianoSuomalainenLatina

1. Problem

Given a non-empty array nums containing only positive integers, please determine whether it is possible to split the array into two subsets so that the sum of the elements of the two subsets is equal.

2. Solution 1

Dynamic programming solution

This problem cannot be solved using a backtracking algorithm, as it will time out if the amount of data is large. We can use dynamic programming.
This question determines whether the sum of the elements in the two parts of an array is equal. First, we need to calculate the sum of all elements in the array, and then determine whether the sum is an even number: if it is not an even number, it means that it is impossible to split it into two completely equal parts, and false is returned directly.
If it is an even number, we only need to determine whether there are some elements whose sum is equal to sum/2. If it is equal to sum/2, then the rest must also be equal to sum/2, which means we can divide the array into two parts with equal sum of elements.
Then the problem is very clear at this time. Assuming sum/2 is the capacity of a backpack, we only need to find some elements and put them into the backpack. If the maximum sum of the elements in the backpack is equal to sum/2, it means that we can divide the array into two equal parts. Isn't this the classic 0-1 backpack problem? The backpack problem series - basic backpack problem, for details, you can see it, I will not repeat it here. Let's find its recursive formula and define dp[i][j] to represent the maximum value obtained by putting the i-th item into a backpack with capacity j.
The value of the i-th item is nums[i -1]:
If nums[i -1]>j, it means that the backpack capacity is insufficient and the i-th item cannot be put in, so we cannot select the i-th item. Then
        dp[i][j]=dp[i -1][j]；
If nums [i -1] <= j, it means that the jth item can be put into the backpack. We can choose to put it in or not, and take the maximum value. If we put it in, it will occupy part of the backpack capacity. The maximum value is
        dp[i][j]=dp[i-1][j-nums[i-1]]+nums[i-1]
If you don't put
        dp[i][j]=dp[i -1][j]；
Take the maximum value of the two

The final recursive formula and code are as follows:

#include <vector>
 
bool canPartition(std::vector<int>& nums) {
    // 计算数组中所有元素的和
    int sum = 0;
    for (int num : nums) {
        sum += num;
    }
    // 如果sum是奇数，说明数组不可能分成完全相等的两份
    if ((sum & 1) == 1) {
        return false;
    }
    // sum除以2
    int target = sum >> 1;
    int length = nums.size();
    std::vector<std::vector<int>> dp(length + 1, std::vector<int>(target + 1, 0));
    for (int i = 1; i <= length; ++i) {
        for (int j = 1; j <= target; ++j) {
            // 下面是递推公式
            if (j >= nums[i - 1]) {
                dp[i][j] = std::max(dp[i - 1][j], dp[i - 1][j - nums[i - 1]] + nums[i - 1]);
            } else {
                dp[i][j] = dp[i - 1][j];
            }
        }
    }
    // 判断背包最大是否能存放和为target的元素
    return dp[length][target] == target;
}

We can also write it like this. The two-dimensional array dp is of boolean type. dp[i][j] indicates whether the sum of the first i elements in the array can be summed to j. Obviously, dp[0][0]=true means that the first 0 elements (that is, no elements) can be summed to 0. The code is as follows

#include <vector>
 
bool canPartition(std::vector<int>& nums) {
    // 计算数组中所有元素的和
    int sum = 0;
    for (int num : nums) {
        sum += num;
    }
    // 如果sum是奇数，说明数组不可能分成完全相等的两份
    if ((sum & 1) == 1) {
        return false;
    }
    // sum除以2得到target
    int target = sum >> 1;
    int length = nums.size();
    std::vector<std::vector<bool>> dp(length + 1, std::vector<bool>(target + 1, false));
    // base case
    dp[0][0] = true;
    for (int i = 1; i <= length; ++i) {
        for (int j = 0; j <= target; ++j) {
            // 递推公式
            if (j >= nums[i - 1]) {
                dp[i][j] = dp[i - 1][j] || dp[i - 1][j - nums[i - 1]];
            } else {
                dp[i][j] = dp[i - 1][j];
            }
        }
    }
    // 返回能否找到和为target的子集
    return dp[length][target];
}

We can see that when calculating the two-dimensional array above, the current value is only related to the upper row, so we can change it to one-dimensional. Note that the second for loop should be reversed, otherwise the previous value will be overwritten and the result will be wrong. Take a closer look
dp[j] = (dp[j] || dp[j - nums [i - 1]]);
It is clear that the value behind the same line depends on the previous one. If it is not reversed, the previous value is modified, and the calculation of the following value will cause an error. Let's take a look at the code

#include <vector>
 
bool canPartition(std::vector<int>& nums) {
    // 计算数组中所有元素的和
    int sum = 0;
    for (int num : nums) {
        sum += num;
    }
    // 如果sum是奇数，说明数组不可能分成完全相等的两份
    if ((sum & 1) == 1) {
        return false;
    }
    // sum除以2得到target
    int target = sum >> 1;
    int length = nums.size();
    std::vector<bool> dp(target + 1, false);
    // base case
    dp[0] = true;
    for (int i = 0; i < length; ++i) {
        // 注意这里j要倒序
        for (int j = target; j >= nums[i]; --j) {
            // 递推公式
            dp[j] = dp[j] || dp[j - nums[i]];
        }
    }
    // 返回能否找到和为target的子集
    return dp[target];
}

3. Solution 2

DFS algorithm solves

Each element can be selected or not. We only need to determine whether the sum of all possible combinations of elements is equal to sum/2. We can think of it as a binary tree. The left child node indicates that the current element is selected, and the right child node indicates that the current element is not selected. As shown in the figure below, the orange node indicates that the current element is selected, and the blue node indicates that it is not selected.

Let's take a look at the preliminary implementation code

#include <vector>
 
bool dfs(const std::vector<int>& nums, int target, int index) {
    // target等于0，说明存在一些元素的和等于sum/2，直接返回true
    if (target == 0) return true;
    // 如果数组元素都找完了，或者target小于0，直接返回false
    if (index == nums.size() || target < 0) return false;
    // 选择当前元素和不选择当前元素两种情况
    return dfs(nums, target - nums[index], index + 1) || dfs(nums, target, index + 1);
}
 
bool canPartition(std::vector<int>& nums) {
    // 计算数组中所有元素的和
    int sum = 0;
    for (int num : nums) sum += num;
    // 如果sum是奇数，说明数组不可能分成完全相等的两份
    if ((sum & 1) == 1) return false;
    // 调用dfs函数
    return dfs(nums, sum >> 1, 0);
}

Unfortunately, because the amount of calculation is too large, it will cause the operation to time out. We can optimize it. Let's take a look at the code

#include <vector>
 
bool dfs(const std::vector<int>& nums, int index, int target, std::vector<std::vector<int>>& map) {
    // target等于0，说明存在一些元素的和等于sum/2，直接返回true
    if (target == 0) return true;
    // 如果数组元素都找完了，或者target小于0，直接返回false
    if (index >= nums.size() || target < 0) return false;
    // 如果此子问题已经被计算过，直接返回结果
    if (map[index][target] != -1) return map[index][target] == 1;
    // 选择当前元素
    bool select = dfs(nums, index + 1, target - nums[index], map);
    // 不选择当前元素
    bool unSelect = dfs(nums, index + 1, target, map);
    // 存储结果，并返回
    map[index][target] = select || unSelect ? 1 : 0;
    return select || unSelect;
}
 
bool canPartition(std::vector<int>& nums) {
    // 计算数组中所有元素的和
    int sum = 0;
    for (int num : nums) sum += num;
    // 如果sum是奇数，说明数组不可能分成完全相等的两份
    if (sum % 2 != 0) return false;
    // sum除以2
    int target = sum / 2;
    std::vector<std::vector<int>> map(nums.size(), std::vector<int>(target + 1, -1));
    return dfs(nums, 0, target, map);
}

4. Solution 3

Bitwise operation solution

Bitwise operations can be used here. The key lies in some restrictions in the question, such as a non-empty array of positive integers, the number of elements in each array will not exceed 100, the size of the array will not exceed 200, etc.
The principle is very simple. We only need to apply for an array bits[ sum+1 ] of size sum+1. The numbers in the array can only be 0 and 1. We can imagine it as a very long binary bit. Since int and long types are too short, we use an array here. Then, every time we traverse an element in the array, such as m, we shift the binary bit to the left by m bits and then perform an OR operation with the original binary bit. Finally, we determine whether bits[ sum/2 ] is 1. If it is 1, true is returned. The text description is not very direct, so let's take Example 1 as an example to draw a picture and see

Finally, you will find a rule that the result of the final operation can be composed of elements in the array as long as it is 1, and it cannot be composed of elements in the array as long as it is 0. After understanding the above process, the code is easy to write. Because we only need to determine whether the middle value in the binary bit is 1, we only need to calculate the low bit, and the high bit does not need to be calculated at all, because it is moved to the left, and the high bit will not have any effect on the middle value, so we can do some optimization here. Finally, let's take a look at the code.

#include <vector>
 
bool canPartition(std::vector<int>& nums) {
    // 计算数组中所有数字的和
    int sum = 0;
    for (int n : nums) {
        sum += n;
    }
    // 如果sum是奇数，直接返回false
    if ((sum & 1) == 1) {
        return false;
    }
    int len = sum / 2;
    // 这里bits的长度是len+1，因为我们只需要计算低位就行了，没必要计算所有的
    std::vector<char> bits(len + 1, 0);
    bits[0] = 1;
    for (int num : nums) {
        for (int j = len - num; j >= 0; j--) {
            bits[j + num] |= bits[j];
        }
        // 判断中位数如果是1，说明可以分成两种相等的子集，直接返回true，不需要再计算了
        if ((bits[len] & 1) != 0) {
            return true;
        }
    }
    return false;
}