416. Partition Equal Subset Sum

发表于 | 分类于 | |

Given a non-empty array containing only positive integers, find if the array can be partitioned into two subsets such that the sum of elements in both subsets is equal.

Note:

  1. Each of the array element will not exceed 100.

  2. The array size will not exceed 200.

Example 1:

1
2
3
4
5
6
7
> Input: [1, 5, 11, 5]
>
> Output: true
>
> Explanation: The array can be partitioned as [1, 5, 5] and [11].
>
>

>

Example 2:

1
2
3
4
5
6
> Input: [1, 2, 3, 5]
>
> Output: false
>
> Explanation: The array cannot be partitioned into equal sum subsets.
>

​ 题意：给出一个数列，判断是否可以把这个数列切割成两部分，使得每部分的和相等。

​ 假设数列的和为sum，很容易可以把问题转化为：数列中是否存在子数列，使得和为sum/2。

​ 一开我的想法还是比较单纯的，就是使用递归（但是不需要回溯，因为不需要记录具体怎么分）。从数列的第i个数开始寻找是否有和为target的子数列，可以分解为从数列的第i+1个数开始寻找是否有和为target或（||）者和为target-nums[i]的子数列。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27

class Solution {
public:
    bool canPartition(vector<int> &nums)
    {
        int sum = 0;
        for (auto i:nums)
            sum += i;
        sort(nums.begin(), nums.end());
        if (sum % 2)
            return false;
        int target = sum / 2;

        return findTargetSum(nums,0,target);

    }

    bool findTargetSum(vector<int> nums, int i, int target)
    {
        if (!target)
            return true;
        if (target < 0 || i == nums.size())
            return false;

        return findTargetSum(nums, i + 1, target) || findTargetSum(nums, i + 1, target - nums[i]);
    }
};

​ 能够样例但是提交上去超时了。理由很简单啊，数组长度最大有200个，那么意味这复杂度为O(2^200)啊，指数增长，不爆炸才怪呢。

​ 其实对于数列中个每个数来说，在组成和为target的问题上，都有两种选择选择：选 or 不选。跟什么问题很像？对，就是耳熟能详的01背包！所以接下来就是如何思考1：定义状态以及2：推导状态转移了。

​ 1：定义状态：dp[i][j]：数列的前i个数是否存在和为j的子数列。

​ 2：状态转移：dp[i][j] = dp[i-1][j] || dp[i-1][ j-nums[i] ]。

​ 因为i的取值范围是0到200，而题目说数列的每个数不会超过100，所以j的最大取值就是200*100 = 20000，整体的复杂度为：20000*200 = 4000000。

​ 本来想到这就可以很容易地写出下面的状态转移代码：

1
2
3
4
5
6
7
for(int i = 1;i < len, i++)
{
  for(int j = 0 ; j <= len*100; j++)
  {
    dp[i][j] = dp[i-1][j] || dp[i-1][j-nums[i]]
  }
}

​ 这样就ok了吗？显然不行，为什么呢？

​ 因为j-nums[i]可能会出现负数啊（最简单就是j=0的时候），这样dp索引负数就出错了。

​ 想到这儿的时候，突然觉得和之前做的494-Target-Sum很相似，同样是01背包问题，也同样会出现索引为负数的情况。

​ 所以我们可以这么转化，既然第i行的数据由第i-1来决定，是否也意味着：第i行的数据会影响到第i+1行？所以就可以上述的状态转移代码改成：

1
2
3
4
5
6
7
8
9
10
11
for (int i = 0; i < len - 1; ++i)
   {
       for (int j = 0; j <= len * 100; ++j)
       {
           if (dp[i][j])
           {
               dp[i + 1][j] = true;
               dp[i + 1][j + nums[i + 1]] = true;
           }
       }
   }

​ 这样就不会出现上述哪个存在索引为负数的情况了！

Code:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39

class Solution {
public:
    bool canPartition(vector<int> &nums)
    {
        int sum = 0;
        int len = nums.size();

        for (auto i:nums)
            sum += i;

        sort(nums.begin(), nums.end());

        if (sum % 2)
            return false;


        vector<vector<bool>> dp(len, vector<bool>(len * 100 + 1, false));

        dp[0][0] = true;
        dp[0][nums[0]] = true;

        for (int i = 0; i < len - 1; ++i)
        {
            for (int j = 0; j <= len * 100; ++j)
            {
                if (dp[i][j])
                {
                    dp[i + 1][j] = true;
                    dp[i + 1][j + nums[i + 1]] = true;
                }
            }
        }

        int target = sum / 2;
        return dp[len - 1][target];

    }
};