Line data    Source code

       1              : // Copyright (c) 2024 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              : 
      17              : #include <numeric>
      18              : #include <vector>
      19              : 
      20              : #include <gtest/gtest.h>
      21              : 
      22              : namespace {
      23              : class Solution {
      24              : public:
      25            4 :     bool canPartition(const std::vector<int>& nums) {
      26            4 :         auto size = static_cast<int64_t>(nums.size());
      27              :         // 只有一个元素的话，无法分成两个非空子集，所以不成立
      28            4 :         if (size < 2)
      29            0 :             return false;
      30            4 :         int sum = std::accumulate(nums.begin(), nums.end(), 0);
      31              :         // 元素和为奇数，无法分成两个正整数之和
      32            4 :         if ((sum & 1) == 1)
      33            1 :             return false;
      34            3 :         int target = sum / 2;
      35              :         // dp[i][j] 表示nums前i个元素中，是否能构成和为j的子集
      36            3 :         std::vector<std::vector<bool>> dp(size + 1, std::vector<bool>(target + 1, false));
      37           14 :         for (int i = 1; i <= size; ++i) {
      38           79 :             for (int j = 1; j <= target; ++j) {
      39              :                 // 当前元素
      40           68 :                 int num = nums[i - 1];
      41           68 :                 if (num == j)
      42           10 :                     dp[i][j] = true;
      43           58 :                 else if (num > j)
      44              :                     // 当前元素比target还大，所以当前元素不能加入到集合中
      45           25 :                     dp[i][j] = dp[i - 1][j];
      46              :                 else
      47           33 :                     dp[i][j] = dp[i - 1][j] || dp[i - 1][j - num];
      48              :             }
      49              :         }
      50            3 :         return dp[size][target];
      51            3 :     }
      52              : };
      53              : } // namespace
      54              : 
      55            4 : TEST(Leetcode, leetcode) {
      56            1 :     Solution s;
      57            1 :     EXPECT_TRUE(s.canPartition({1, 5, 11, 5}));
      58            1 :     EXPECT_TRUE(s.canPartition({2, 2, 1, 1}));
      59            1 :     EXPECT_FALSE(s.canPartition({1, 2, 5}));
      60            1 :     EXPECT_FALSE(s.canPartition({1, 2, 3, 5}));
      61            1 : }