本题有一个很直观的思路是直接用类似DFS的解法，但是在leetcode上面超时了。
    于是采用dynamic programming的解法：
    核心逻辑：

    1. partition[i][j] = (partition[i-1][j] || partition[i-1][j-nums[i]]);
    • i这个维度是指截止到nums array的第i个元素。
    • j是subset的和

    • partition[i][j]是指截止到第i个元素，是否能组成一个和为j的subset

      1. class Solution {
      2. public:
      3.   bool canPartition(vector<int>& nums) {
      4.       int target = accumulate(nums.begin(), nums.end(), 0);
      5.       if (target % 2 != 0) {
      6.           return false;
      7.       }
      8.       target /= 2;
      9.       int sz = nums.size();
      10.       bool partition[sz][target+1];
      11.       for (int i = 0; i < sz; ++i) {
      12.           for (int j = 0; j <= target; ++j) {
      13.               partition[i][j] = false;
      14.           }
      15.       }
      16.       if (nums[0] <= target) {
      17.           partition[0][nums[0]] = true;
      18.       }
      19.       for (int i = 0; i < sz; ++i) {
      20.           partition[i][0] = true;
      21.       }
      22.       for (int i = 1; i < sz; ++i) {
      23.           for (int j = 1; j <= target; ++j) {
      24.               if (j >= nums[i]) {
      25.                   partition[i][j] = (partition[i-1][j] || partition[i-1][j-nums[i]]);
      26.               }
      27.               else {
      28.                   partition[i][j] = partition[i-1][j];
      29.               }
      30.           }
      31.       }
      32.       return partition[sz-1][target];
      33.   }
      34. };

    • 本题并不难，关键在于理解nums的总和并不会是一个很大的数，可以放心大胆地用dynamic programming