Line data    Source code

       1              : // Copyright (c) 2023 The Authors. All rights reserved.
       2              : //
       3              : // Licensed under the Apache License, Version 2.0 (the "License");
       4              : // you may not use this file except in compliance with the License.
       5              : // You may obtain a copy of the License at
       6              : //
       7              : //      https://www.apache.org/licenses/LICENSE-2.0
       8              : //
       9              : // Unless required by applicable law or agreed to in writing, software
      10              : // distributed under the License is distributed on an "AS IS" BASIS,
      11              : // WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
      12              : // See the License for the specific language governing permissions and
      13              : // limitations under the License.
      14              : 
      15              : // Authors: liubang (it.liubang@gmail.com)
      16              : // Created: 2023/04/16 17:19
      17              : 
      18              : #include <numeric>
      19              : #include <vector>
      20              : 
      21              : #include <gtest/gtest.h>
      22              : 
      23              : namespace {
      24              : class Solution {
      25              : public:
      26            4 :     bool canPartition(const std::vector<int>& nums) {
      27            4 :         auto size = static_cast<int64_t>(nums.size());
      28              :         // 只有一个元素的话，无法分成两个非空子集，所以不成立
      29            4 :         if (size < 2)
      30            0 :             return false;
      31            4 :         int sum = std::accumulate(nums.begin(), nums.end(), 0);
      32              :         // 元素和为奇数，无法分成两个正整数之和
      33            4 :         if ((sum & 1) == 1)
      34            1 :             return false;
      35            3 :         int target = sum / 2;
      36              :         // dp[i][j] 表示nums前i个元素中，是否能构成和为j的子集
      37            3 :         std::vector<std::vector<bool>> dp(size + 1, std::vector<bool>(target + 1, false));
      38           14 :         for (int i = 1; i <= size; ++i) {
      39           79 :             for (int j = 1; j <= target; ++j) {
      40              :                 // 当前元素
      41           68 :                 int num = nums[i - 1];
      42           68 :                 if (num == j)
      43           10 :                     dp[i][j] = true;
      44           58 :                 else if (num > j)
      45              :                     // 当前元素比target还大，所以当前元素不能加入到集合中
      46           25 :                     dp[i][j] = dp[i - 1][j];
      47              :                 else
      48           33 :                     dp[i][j] = dp[i - 1][j] || dp[i - 1][j - num];
      49              :             }
      50              :         }
      51            3 :         return dp[size][target];
      52            3 :     }
      53              : };
      54              : } // namespace
      55              : 
      56            4 : TEST(Leetcode, leetcode) {
      57            1 :     Solution s;
      58            1 :     EXPECT_TRUE(s.canPartition({1, 5, 11, 5}));
      59            1 :     EXPECT_TRUE(s.canPartition({2, 2, 1, 1}));
      60            1 :     EXPECT_FALSE(s.canPartition({1, 2, 5}));
      61            1 :     EXPECT_FALSE(s.canPartition({1, 2, 3, 5}));
      62            1 : }