1
class Solution {
2
 public:
3
  bool canPartition(vector<int> &nums) {
4
    int sum = 0;
5
    int n = nums.size();
6
    for (int i = 0; i < n; i++) sum = sum + nums[i];
7
    cout << sum;
8

9
    if (sum % 2 == 0) {
10
      int s = sum / 2;
11
      int t[n + 1][s + 1];
12
      for (int i = 0; i < s + 1; i++) t[0][i] = false;
13
      for (int i = 0; i < n + 1; i++) t[i][0] = true;
14

15
      for (int i = 1; i < n + 1; i++) {
16
        for (int j = 1; j < s + 1; j++) {
17
          if (nums[i - 1] <= j)
18
            t[i][j] = t[i - 1][j - nums[i - 1]] || t[i - 1][j];
19
          else
20
            t[i][j] = t[i - 1][j];
21
        }
22
      }
23
      return t[n][s];
24
    } else
25
      return false;
26
  }
27
};