https://programmercarl.com/0416.%E5%88%86%E5%89%B2%E7%AD%89%E5%92%8C%E5%AD%90%E9%9B%86.html

视频讲解：https://www.bilibili.com/video/BV1rt4y1N7jE

1.本题一开始我想直接用回溯算法搜索来着，但是卡哥说会超时，然后试着往01背包靠，一开始做的时候的疑问就是这也没有重量和价值呀，做着做着就有点点思路发现，重量和价值应该就是一个意思就是数组的值，没想明白的是这个dp数组的含义，依本题题意我们要求的就是二分之数组值之和为要求的背包容量，通过一维滑动数组来求每一层的数值，其实还是在理解上有点偏差，就是在遍历顺序上在第二层循环变量背包容量的地方我在终止条件处卡住了，终止条件就是这个背包容量至少要大于本层选择的这个数，要不就没有意义了。

CPP

class Solution {
public:
    bool canPartition(vector<int>& nums) {
    //     sort(nums.begin(), nums.end());
    //     vector<int> sum(nums.size(), 0);
    //     for(int i = 1; i < nums.size(); i++){
    //         sum[i] += sum[i - 1];
    //     }
    //     vector<int> dp(10001, 0);

    //     for(int i = 0; i < nums.size(); i++){
    //         for(int j = sum[nums.size() - 1]; j >= nums[i]; j--){
    //             dp[j] = max(dp[j], dp[j - nums[i]] + nums[i]);
    //         }
    //     }
    // }
        vector<int> dp(10001, 0);
        int sum = 0;
        for(int i = 0; i < nums.size(); i++){
            sum += nums[i];
        }
        int target = sum/2;
        if(sum % 2 == 1)return false;
        for(int i = 0; i < nums.size(); i++){
            for(int j = target; j >= nums[i]; j--){
                dp[j] = max(dp[j], dp[j - nums[i]] + nums[i]);
            }
        }
        if(dp[target] == target){
            return true;
        }
        return false;
    }
};