CareerCup

Simply adding pounds to already existing possibilities (~dynamic programming in 1d array)

1) 
 Initialize: use 0 pounds -> output.add(0) 
2)
 Foreach notProcessedPound in pounds:
  Foreach value in output:
   PosibleNewValue1 =  value + notProcessedPound.weight
   PosibleNewValue2 =  value - notProcessedPound.weight
   if (!PosibleNewValue1 is in output && PosibleNewValue1 > 0 ):
    output.add(PosibleNewValue1)
   if (!PosibleNewValue2 is in output && PosibleNewValue2 > 0 ):
    output.add(PosibleNewValue2)

You missed 350.

Assuming it is a two pan balance, and we are allowed to place weight in any pan.

Each weight has 3 states: Left pan, not in any pan, Right pan.

Assign being in left pan as -1, and right pan as 1.

In each possible weighing, each weight w_i gets a coefficient a_i where a_i is -1, 0 or 1.

The weight that can be measured is the absolute value of a_1 w_1 + a_2 w_2 + ... + a_n w_n.

This gives us an algorithm.

Try to enumerate possible coefficients (a_1, a_2, .., a_n) and compute.

This can be done using the odometer trick, or if n is small enough, interpreting as a base 3 number.

This will visit each weight at least twice, but is asymptotically optimal in the worst case(the case when all weights are powers of 3, you will have Theta(3^n) possible measurements).

Here is quick python code

def generate_odometer(limits_list):
	odometer_list = map(lambda x: 0, limits_list)
	has_more = True
	n = len(odometer_list)
	while has_more:
		yield odometer_list
		has_more = False
		for j in range(0,n):
			limit = limits_list[j]
			if odometer_list[j] < limit-1:
				odometer_list[j] = odometer_list[j]+1
				has_more = True
				break
			else:
				odometer_list[j] = 0;
				continue
  
def weights(lst):
	feasible = {}
	limits_list = map(lambda x:3, lst)
	# 2 is treated as -1
	for coeffs in generate_odometer(limits_list):
		sum,idx = 0,0
		for coeff in coeffs:
			if coeff == 2:
				sum -= lst[idx]
			if coeff == 1:
				sum += lst[idx]
			idx += 1
		if sum < 0:
			sum = -sum
		feasible[sum] = True
   
	print feasible.keys()				
    
def main():
        weights([100,250])
	weights([1,3,9,27])
   
if __name__ == "__main__":
	main()

and here is the output

[0, 250, 100, 150, 350]
[0, 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, 40]

so, any given weight can be of three forms

(-1, 0, 1) where

-1 : when is on the left side(i.e. its weight is getting subtracted)
0: not on any side (does not contribute to the weight)
1: when it is on the right side (i.e. its weight is getting added).

So, for n weights, the answer will be permutation of (-1, 0, 1) + (-1, 0, 1) + ..... + n times..where for any weight choices are: (-1, 0, 1).

Valid answers are sum greater than zero.
Taking example from the question, weights are 100, 250. Thus, the combination will be

(-1, 0, 1) + (-1, 0, 1)

-1 + -1 = -100 + -250 = invalid
-1 + 0 = -100 + 0 = invalid
-1 + 1 = -100 + 250 = 150
0 + -1 = 0 + -250 = invalid
0 + 0 =  0 + 0 = invalid
0 + 1 = 0 + 250 = 250
1 + -1 = 100 + -250 = invalid
1 + 0 = 100 + 0 = 100
1 + 1 = 100 + 250 = 350

thus making 100, 250, 150, 350 as answer.

comment if you find any bug with the logic

Thanks :)

Here is the CPP code for the above question.
Since all the answers will be between Zero and Sum of all the weights. I initialized an array of that length of structure node. (see code). For every weight, I check the previous entries and find the every new possible answer.
The code runs in time complexity O(n^2).

#include<iostream>

using namespace std;

typedef struct node
{	
	bool present;
	int small;
	int large;
}node;

int main()
{
	cout << "Enter the number of values you want to enter\n";
	int num,sum=0;
	cin >> num;
	int* array = new int[num];
	cout << "Enter the numbers\n";
	for(int i = 0; i < num; i++)
	{
		cin >> array[i];
		sum +=array[i];
	}

	node* result = new node[sum+1];
	for(int i = 0; i <= sum; i++)
		result[i].present = false;

	result[0].present = true;
	result[0].small = 0;
	result[0].large = 0;

	sum = 0;
	for(int i=0; i<num; i++)
	{
		sum += array[i];
		for(int j = 0; j <= sum; j++)
		{
			if(result[j].present == true)
			{
				if(result[result[j].large + array[i]].present == false)
				{
					result[result[j].large + array[i]].present = true;
					result[result[j].large + array[i]].small = 0;
					result[result[j].large + array[i]].large = result[j].large + array[i];
				}
				if(result[result[j].small + array[i]].present == false)
				{
					result[result[j].small + array[i]].present = true;
					result[result[j].small + array[i]].small = 0;
					result[result[j].small + array[i]].large = result[j].small + array[i];
				}
				if(result[result[j].large + array[i] - result[j].small].present == false)
				{
					result[result[j].large + array[i] - result[j].small].present = true;
					result[result[j].large + array[i] - result[j].small].small = result[j].small;
					result[result[j].large + array[i] - result[j].small].large = result[j].large + array[i];
				}
				if((result[j].small + array[i] - result[j].large) > 0)
				if(result[result[j].small + array[i] - result[j].large].present == false)
				{
					result[result[j].small + array[i] - result[j].large].present = true;
					result[result[j].small + array[i] - result[j].large].small = result[j].large;
					result[result[j].large + array[i] - result[j].small].large = result[j].small + array[i];
				}
			}
		}
	}	
	for(int i = 0; i<= sum; i++)
	{
		if(result[i].present == true)
			cout << i << " ";
	}
	cout << endl;
	delete result;
	delete array;
	return 0;
}

I think the problem is NP complete problem and we don't have any polynomial solution we can possibly check for all combination,
so what we need to do is to calculate

choose k numbers and sum them, 
choose r numbers from remaining ones and sum them 
and calculate difference.
Now this k vary from 1 to N and r vary from 1 to N-k, 
so the complexity goes to exponential.