416. Partition Equal Subset Sum

416. Partition Equal Subset Sum (Medium)

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:

Input: [1, 5, 11, 5]

Output: true

Explanation: The array can be partitioned as [1, 5, 5] and [11].

 

Example 2:

Input: [1, 2, 3, 5]

Output: false

Explanation: The array cannot be partitioned into equal sum subsets.

 

Related Topics:
Dynamic Programming

Similar Questions:

• Partition to K Equal Sum Subsets (Medium)

Solution 1.

// OJ: https://leetcode.com/problems/partition-equal-subset-sum/
// Author: github.com/lzl124631x
// Time: O(2^N)
// Space: O(2^N)
class Solution {
public:
    bool canPartition(vector<int>& A) { 
        int total = accumulate(begin(A), end(A), 0);
        if (total % 2) return false;
        unordered_set<int> s, next;
        for (int n : A) {
            next = s;
            for (int m : s) next.insert(m + n);
            next.insert(n);
            if (next.count(total / 2)) return true;
            swap(s, next);
        }
        return false;
    }
};

Solution 2. 0-1 Knapsack

Let dp[i+1][j] be whether we can sum to j using numbers in A[0] to A[i].

We have two options for dp[i+1][j]:

• We skip A[i]. Then dp[i+1][j] = dp[i][j].
• We pick A[i]. Then dp[i+1][j] = dp[i][j-A[i]].

dp[i+1][j] = dp[i][j] || (j >= A[i] && dp[i][j - A[i]])

dp[i][0] = true where 0 <= i <= N

// OJ: https://leetcode.com/problems/partition-equal-subset-sum/
// Author: github.com/lzl124631x
// Time: O(NS)
// Space: O(NS)
class Solution {
public:
    bool canPartition(vector<int>& A) {
        int sum = accumulate(begin(A), end(A), 0), N = A.size();
        if (sum % 2) return false;
        sum /= 2;
        vector<vector<bool>> dp(N + 1, vector<bool>(sum + 1));
        for (int i = 0; i <= N; ++i) dp[i][0] = true;
        for (int i = 0; i < N; ++i) {
            for (int j = 1; j <= sum; ++j) {
                dp[i + 1][j] = dp[i][j] || (j >= A[i] && dp[i][j - A[i]]);
            }
        }
        return dp[N][sum];
    }
};

Solution 3. 0-1 Knapsack with Space Optimization

Since dp[i + 1][j] is only dependent on values in the previous row, we can reduce the size of the dp array from N * S to 1 * S.

// OJ: https://leetcode.com/problems/partition-equal-subset-sum/
// Author: github.com/lzl124631x
// Time: O(NS)
// Space: O(S)
class Solution {
public:
    bool canPartition(vector<int>& A) {
        int sum = accumulate(begin(A), end(A), 0), N = A.size();
        if (sum % 2) return false;
        sum /= 2;
        vector<bool> dp(sum + 1);
        dp[0] = true;
        for (int i = 0; i < N; ++i) {
            for (int j = sum; j >= A[i]; --j) {
                dp[j] = dp[j] || dp[j - A[i]];
            }
        }
        return dp[sum];
    }
};

Or

// OJ: https://leetcode.com/problems/partition-equal-subset-sum
// Author: github.com/lzl124631x
// Time: O(NS)
// Space: O(S) where S the sum of nums.
class Solution {
private:
  bool subsetSum(vector<int> &nums, int S) {
    vector<int> dp(S + 1);
    dp[0] = 1;
    for (int n : nums)
      for (int i = S; i >= n; --i) dp[i] += dp[i - n];
    return dp[S];
  }
public:
  bool canPartition(vector<int>& nums) {
    int sum = accumulate(nums.begin(), nums.end(), 0);
    return sum % 2 == 0 && subsetSum(nums, sum / 2);
  }
};

Solution 4. DP

Create a bitmask bits of size MAX_NUM * MAX_ARRAY_SIZE / 2 + 1. If we can sum to i, then bits[i] = 1; otherwise bits[i] = 0.

When we use A[i] to update the result, we add A[i] to all the numbers that we can form previously, i.e. bits << n.

We merge the result using bits |= bits << n.

bits[sum / 2] is the result.

// OJ: https://leetcode.com/problems/partition-equal-subset-sum
// Author: github.com/lzl124631x
// Time: O(N)
// Space: O(MAX_NUM * MAX_ARRAY_SIZE)
// Ref: https://discuss.leetcode.com/topic/62334/simple-c-4-line-solution-using-a-bitset
class Solution {
public:
    bool canPartition(vector<int>& A) {
        const int MAX_NUM = 100, MAX_ARRAY_SIZE = 200;
        bitset<MAX_NUM * MAX_ARRAY_SIZE / 2 + 1> bits(1);
        int sum = accumulate(begin(A), end(A), 0);
        if (sum % 2) return false;
        for (int n : A) bits |= bits << n;
        return bits[sum / 2];
    }
};