CareerCup

Basically the same problem as the "Combination Sum" problem in leetcode.

S = 0;
     for (int i=0; i < N; i++)
             S += a[i];
     S = S/2; 
     int dp[N][S+1];
     memset(dp, 0, sizeof(dp)) ; 
     dp[0][0] = 1;
     for (int j=0; j <= S j++)
            if (j >= a[0]) dp[j] = 1;
      for (int i=1; i < N; i++)
             for (int j=0; j <= S; j++) {
                        dp[i][j] = dp[i-1][j];
                        if (j >= a[i]) dp[i][j] += dp[i-1][j-a[i]];
             }
      return dp[N-1][S]; // returns number of subsets

Partition problem : pseudo polynomial time solution:

import sys
import argparse

def partition(arr, n):
    if arr is None:
        return "Error: No array provided";
    'solved via dynamic programming approach'
    p = [[0 for x in xrange(arr.__len__() + 1)] for x in xrange(n / 2 + 1)];
    initGraph(p, n / 2, arr.__len__());
    
    '''Apply dynamic programming approximation
    
       P(i,j) = P(i, j-1) or P(i-xj, j-1) 
    
    '''
    res = setUpGraph(arr, p, n / 2, arr.__len__());
    if res is None:
        return "Error: No graph returned!";
    else:
        return res[n / 2][arr.__len__()];
    

def setUpGraph(arr, p, rows, cols):
    i = 1;
    j = 1;
    while i <= rows:
        j = 1;
        while j <= cols:
            p[i][j] = p[i][j - 1] | p[i - int(arr[j - 1])][j - 1];
            j = j + 1;
        i = i + 1;
    return p;    
    
def initGraph(p, rows, cols):
    i = 0;
    while i <= cols:
        'set first row to True'
        p[0][i] = True;
        i = i + 1;
    i = 1;
    while i <= rows:
        'set first col to False except p[0][0]'
        p[i][0] = False;
        i = i + 1;

Do we need to find a subset whose sum matches at most K/2 or the total number of subsets ??
please clarify everyone??

it is basically a problem of finding the subset sum with sum r/2 where r is the sum of the array. This code prints all the necessary subsets possible for summing upto r/2

#include <stdio.h>
#include <stdlib.h>
int arr1[]={6,5,4,3,2,1};
int sumOfSubset(int s,int k,int w[],int r,int n,int m,int x[])
{
    int i,j,sum=0;
    x[k]=1;
    if(s+w[k]==m)
    {
        for(i=0;i<n;i++)
        {
            if(x[i]==1)
            {
                for(j=0;j<n;j++)
                {
                    if(w[i]==arr1[j])
                    {
                        printf("%d",j);
                    }

                }
            }
        }
        printf("\n");
    }
    else if(s+w[k]+w[k+1]<=m)
        sumOfSubset(s+w[k],k+1,w,r-w[k],n,m,x);
    if((s+r-w[k]>=m)&&(s+w[k+1])<=m)
    {
        x[k]=0;
        sumOfSubset(s,k+1,w,r-w[k],n,m,x);
    }
}
int main()
{
    int arr[]={6,5,4,3,2,1};
    int n=sizeof(arr)/sizeof(arr[0]);
    int i,r=0;
    int x[n];
    for(i=0;i<n;i++)
    {
        x[i]=0;
    }
    for(i=0;i<n;i++)
    {
        r=r+arr[i];
    }
    sumOfSubset(0,0,arr,r,n,r/2,x);
}

I see very complicated solutions not sure why they are not making any sense to me.
I'll do mine using C#.
I'm pretty much creating a hash of all unique numbers and their total occurrences then I use each number to see if the adding them conforms with the wanted total.

I also do some checks in order to determine if the array is valid to do this operation because the question ask to give exactly half the total sum.

List<int> HalfTotalSubSet(int[] input)
{
        // This is to store each number and how many occurrences are found
	Dictionary<int, int>  numberHash = new Dictionary<int, int>();
	int total = 0;

	foreach (int n in numbers)
	{
		if(!numberHash.ContainsKey(n))
		{
			numberHash.Add(n, 1);
		}
		else
		{
			numberHash[n]++;
		}

		total += n;
	}

	if (total%2 != 0)
	{
		throw new ArgumentException(
			 "The total sum of the array is an even number.\nTotal: " + total);
	}

	List<int> subset = new List<int>();
	if(TotalSumSubSetCore(numberHash, subset, total/2))
	{
		return subset;
	}
	
	// Either this or just return an empty subset or null. I'm leaving it implicit for now.
	throw new ArgumentException(
		"There is no subset that sum half the total.\nTotal:" + total);
}

bool TotalSumSubSetCore(Dictionary<int, int> numberHash, List<int> subset, int sum)
{
	foreach(KeyValuePair nh in numberHash)
	{
		if(nh.Value > 0)
		{
			int newSum = sum - nh.Key;

			// This means that there are no remaining numbers to process
			if(newSum == 0)
			{
				subset.Add(nh.Key);
				return true;
			}
			
			// This assuming that they are non-negative numbers otherwise there is not
			// no need to have to do this check but it will go through all numbers assuming
			// that there is one that could be negative and make it sum equal to zero.
			if(newSum < 0)
			{
				continue;
			}
			
			nh.Value--;

			if(TotalSumSubSetCore(numberHash, subset, newSum))
			{
				subset.Add(nh.Key);
				return true;
			}

			nh.Value++;
		}
	}
	
	// This means that no number could give the exact sum.
	return false;
}

sort first, then two pointers, one at the beginning and another at the end. moving towards the middle

Essentially you would have to sort the list, then cycle from the front to back decreasing your back pointer towards the front each time you have cycled thru and not found the correct sum. Function in Ruby

def halfSum (nums, sum)

	front = 0
	back = nums.length - 1
	currBack = 0
	currFront = 0
	i = 0

	nums.sort!
	
	while back > 1
		currBack = nums[back]
		back -= 1
		i = 0
		
		while i < back
			currFront += nums[i]
			
			if(currFront + currBack == sum/2)
				return nums[0, i].concat( nums[back, nums.length-1] )
			elseif(currFront + currBack > sum/2)
				break
			else
				i+=1
			end
		end
	end
	return -1
end