My solution to a “Daily Coding Problem” that I received in my mail today.

Given a multiset of integers, return whether it can be partitioned into two subsets whose sums are the same.

For example, given the multiset {15, 5, 20, 10, 35, 15, 10}, it would return true, since we can split it up into {15, 5, 10, 15, 10} and {20, 35}, which both add up to 55.

Given the multiset {15, 5, 20, 10, 35}, it would return false, since we can’t split it up into two subsets that add up to the same sum.

Here’s my solution in Typescript,

sixty(arr: number[]): boolean {
    if(arr == null) {
        return false;
    }
    //step 1: check if the sum is odd?
    const reducer = (v1: number, v2: number) => v1 + v2;
    let total = arr.reduce(reducer);
    if(total % 2 != 0) {
        //if so then it's impossible to find 2 'equal' partitions
        return false;
    }
    var returnVal = true;
    let half = total / 2;
    //get half and then find 2 subsets that total upto that no
    return this.hasSubset(arr, arr.length, total / 2);
}
private hasSubset(arr: number[], idx: number, sum: number): boolean {
    if(sum == 0) {
        return true;
    } else if(idx == 0 && sum != 0) {
        return false;
    }
    if(arr[idx - 1] > sum) {
        return this.hasSubset(arr, idx - 1, sum);
    } 
    return this.hasSubset(arr, idx - 1, sum)
    || this.hasSubset(arr, idx -1 , sum - arr[idx -1] );
}

Like the blog? Subscribe for updates

As usual, if you find any of my posts useful support me by  buying or even trying one of my apps on the App Store. 

https://mydaytodo.com/apps/

Also, if you can leave a review on the App Store or Google Play Store, that would help too.


0 Comments

Leave a Reply

Your email address will not be published. Required fields are marked *