number of combinations

[chaos007]

hi,
i am having trouble with making a program that will tell you the number of ways you can do something. for example, say there are 5 numbers, 8,1,2,1,6 and i have to add them and make 10, using the least numbers. so, 8+2=10, 8+1+1=10, 6+1+1+2=10. in this case, 8 and 2 are the numbers i want to output because they make ten and only 2 numbers are used.8+1+1 and 6+1+1+2 are more than 2 numbers, so, 8+2 will be chosen over them. how can i write a program for this. (in this case it asks for the least amount of numbers, i am having trouble figuring out the most number of combinations as well). thanx a lot.

 

[Zyrenthian]

here is how I wouled approach it (I am assuming no negative numbers... if you are allowing them, you can make some minor mods)

Steps:
sort the nubmers.

Discard any numbers taht exceed the desired value.

Verify that the largest value does not equal the desired value.

If the number is even and only one odd number exists, remove the odd number.

If the number is odd and no odd numbers exist there is no solution.

Now, Choose the largest number, subtract that from the desired value and compute how many numbers in the given list will add up to the difference... rinse and repeat (recursion). Once done with that number, you know all possible combinations for that number have been calculated and you can discard any occurances of that number.

That should get you started As I said, some modifications will be required if negative numbers are allowed.

Matt