LeetCode#416

LeetCode#416分割等和子集

题目链接
题面很简单，意思就是给你个数组，然后问能否把这个数组分成加和相等的两个子数组，能的话返回true，否则返回false。首先能想到以下几种一定返回false：

• 如果加和的sum为奇数则一定不能等分
• 如果数组中的元素数量n<2一定不能等分
• 如果数组中有一个元素大于sum/2一定不能等分（为了降低时间复杂度，我们只需要判断数组中最大的数和sum/2的关系即可）
  一开始我的想法是使用递归，遍历一遍整个数组，在每个数上判断一下选择或者不选择，但是直接tle了（这样递归的时间复杂度是2^n，我算成n^2了人傻了）
  附一个递归的代码：

  class Solution {
  public:
      void dfs(vector<int>& nums,int pos,int cnt,int& sum,bool& flag)
      {
          if(cnt == sum)
          {
              flag = true;
              return;
          }
          if(cnt > sum)
              return;
          if(pos == nums.size())
              return;
          dfs(nums,pos+1,cnt+nums[pos],sum,flag);
          dfs(nums,pos+1,cnt,sum,flag);
      }
      bool canPartition(vector<int>& nums) {
          int sum = 0;
          bool flag = false;
          for(int i = 0 ; i < nums.size() ; i++)
              sum += nums[i];
          if(sum%2==1)
              return false;
          else
          {
              sum/=2;
              dfs(nums,0,0,sum,flag);
          }
          return flag;
      }
  };

  而正确的解法应该是使用动态规划，和我的想法差不多，也是判断每个数选择或者不选择，这样就可以把这道题模型化为01背包还是菜没想到
  dp[i][j]的含义是当使用数组中的前i个数，能否组合成j
  初始化dp数组有几个情况：
• 当i=0的时候，即只使用数组中第0个数，dp[0][num[0]]=true
• 当j=0的时候，不选择任何数即可满足条件，所以dp[i][0]=true
  dp[i][num[i]]=true也是成立的，但是好像没啥用
  动态转移方程分为两种情况：
• 选取num[i],dp[i][j] = dp[i-1][j-num[i]]
• 不选取num[i],dp[i][j]=dp[i-1][j]

附代码之前，再记录两个从来没用过的函数，accumulate()和*max_element()。
accumulate()函数在#include头文件中，作用是累加求和，当然，你也可以自定义类型求和(数据处理)。accumulate带有三个形参：头两个形参指定要累加的元素范围，第三个形参则是累加的初值，例如：

int sum = accumulate(vec.begin() , vec.end() , 42);  //求vector容器所有元素的累加和，累加初值设为42

还有种另类用法是将整形vector转换为字符串，例如：

string sum = accumulate(v.begin() , v.end() , string(" "));

max_element()函数，返回容器中的最大值，相对应的，min_element()函数返回容器/数组中的最小值，它们都在#include头文件中。

附代码：

class Solution {
public:
    bool canPartition(vector<int>& nums) {
        int n = nums.size();
        if (n < 2) {
            return false;
        }
        int sum = accumulate(nums.begin(), nums.end(), 0);
        int maxNum = *max_element(nums.begin(), nums.end());
        if (sum & 1) {
            return false;
        }
        int target = sum / 2;
        if (maxNum > target) {
            return false;
        }
        vector<vector<int>> dp(n, vector<int>(target + 1, 0));
        for (int i = 0; i < n; i++) {
            dp[i][0] = true;
        }
        dp[0][nums[0]] = true;
        for (int i = 1; i < n; i++) {
            int num = nums[i];
            for (int j = 1; j <= target; j++) {
                if (j >= num) {
                    dp[i][j] = dp[i - 1][j] | dp[i - 1][j - num];
                } else {
                    dp[i][j] = dp[i - 1][j];
                }
            }
        }
        return dp[n - 1][target];
    }
};