解法一

1、思路

• 若数组nums中所有元素的和为sum，题目的问题可以转化为：能否从数组中找若干元素，使得它们的和为sum / 2。因为如果满足以上条件，剩下的元素和也为sum / 2；

• dp[i][j]表示能否从前i个物品中选择若干物品放满容量为j的背包，每次dp有两种选项，选择当前物品或者不选当前物品，即当前状态可以由两种状态转移而来：

  • 选择将标号为i - 1的物品放入背包中，若能从前i - 1件物品中选择若干物品放满容量为j - nums[i - 1]的背包（即dp[i - 1][j - nums[i - 1] = true）则dp[i][j] = true；

  • 选择不将标号为i - 1的物品放入背包中，若能从前i - 1件物品中选择若干物品放满容量为j的背包（即dp[i - 1][j] = true），那么dp[i][j] = true；

• 初始化dp[i][0] = true，因为只要在前i件物品中取0件物品，那么容量肯定是0；

• 时间复杂度为 $O(NT)$ ，空间复杂度为 $O(NT)$ ，其中 $N$ 表示数组长度， $T$ 表示目标和。

2、代码

class Solution {
public:
    bool canPartition(vector<int>& nums) {
        int sum = 0;
        for (int &i : nums) sum += i;       //计算数组和

        if (sum % 2 == 1) return false;     //和为奇数，肯定无法等分

        vector<vector<bool>> dp(nums.size() + 1, vector<bool>(sum / 2 + 1));
        for (int i = 0; i < nums.size(); ++ i)
        {
            dp[i][0] = true;                //初始化
        }

        for (int i = 1; i <= nums.size(); ++ i)
        {
            for (int j = 1; j <= sum / 2; ++ j)
            {
                dp[i][j] = dp[i - 1][j];                //不选的情况
                if (!dp[i][j] && j >= nums[i - 1])      //当前物品价值不能大于总价值，否则会数组越界
                {
                    dp[i][j] = dp[i - 1][j - nums[i - 1]];  //选的情况
                }
            }
        }

        return dp[nums.size()][sum / 2];
    }
};

解法二：空间效率优化

1、思路

• 当前状态dp[i][j]只与两个状态有关：dp[i - 1][j]和dp[i - 1][j - nums[i - 1]]，可以用一个一维数组来做dp；

• 要注意从右往左进行填充，因为dp[i - 1][j]在计算完dp[i][j]之后还可能在计算右边的其他值时用到；

• 时间复杂度为 $O(NT)$ ，空间复杂度为 $O(T)$ ，其中 $N$ 表示数组长度， $T$ 表示目标和。

2、代码

class Solution {
public:
    bool canPartition(vector<int>& nums) {
        int sum = 0;
        for (int &i : nums) sum += i;

        if (sum % 2 == 1) return false;

        vector<bool> dp(sum / 2 + 1);
        dp[0] = true;

        for (int i = 1; i < nums.size(); ++ i)
        {
            for (int j = sum / 2; j >= 0; -- j)     //从右往左填充
            {
                if (!dp[j] && j >= nums[i - 1])
                {
                    dp[j] = dp[j - nums[i - 1]];
                }
            }
        }

        return dp[sum / 2];
    }
};