Sunday, November 6, 2016

LeetCode OJ - Partition Equal Subset Sum

Problem:

Please find the problem here.

Analysis: 

This is basically set partition, a NP complete problem. The numeric range is small, so we will leverage that to produce a fast enough solution.

Solution:

We maintain a bit vector that represents the achievable sum. Initially, only 0 is achievable (by summing up no numbers). For each number nums[i], for each achievable number k,  we know nums[i] + k is achievable.

Note that in the loop, I test and set the bit vector in reverse order. This is on purpose to make sure each achievable number we read does indeed come from the previous iteration. That save us from having them more than 1 buffers.

Code:

#include "stdafx.h"

// https://leetcode.com/problems/partition-equal-subset-sum/

#include "LEET_PARTITION_EQUAL_SUBSET_SUM.h"
#include <map>
#include <iostream>
#include <sstream>
#include <vector>
#include <string>

using namespace std;

namespace _LEET_PARTITION_EQUAL_SUBSET_SUM
{
    class Solution {
    public:
        bool canPartition(vector<int>& nums)
        {
            int sum = 0;
            for (int i = 0; i < nums.size(); i++)
            {
                sum += nums[i];
            }
            if (sum % 2 == 0)
            {
                sum /= 2;
                vector<bool> can_reach;
                can_reach.resize(sum + 1, false);
                can_reach[0] = true;
                for (int i = 0; i < nums.size(); i++)
                {
                    for (int j = sum - nums[i]; j >=0 ; j--)
                    {
                        if (can_reach[j])
                        {
                            can_reach[j + nums[i]] = true;
                            if (j + nums[i] == sum)
                            {
                                return true;
                            }
                        }
                    }
                }
            }
            return false;
        }
    };
};

using namespace _LEET_PARTITION_EQUAL_SUBSET_SUM;

int LEET_PARTITION_EQUAL_SUBSET_SUM()
{
    Solution solution;
    int input_array[] = { 1, 11, 5 ,5};
    vector<int> input(input_array, input_array + _countof(input_array));
    cout << solution.canPartition(input) << endl;
    return 0;
}

No comments :

Post a Comment