March 8th, 2012, 08:05 AM  #1 
Newbie Joined: Apr 2011 Posts: 7 Thanks: 0  Algorithm question
Hi all, I'm trying to find an algorithm  no code, just words on paper  and I'm running into a wall here. The input is an array A[1..n] of n different integers, and an integer, b The question is in how many ways can b be written as the sum of elements of the array when any element A[i] can be used in the sum at most once. I'm looking for a solution that runs at O(nb) time. It seems like a dynamic approach is the only way this is going to work, but I can't really think of a subproblem that I could break it up into; it doesn't seem like it should be too difficult, but I'm totally hitting a wall. (also, in case its not clear, i'm *pretty* sure the integers in the array increase by 1 each time, i.e. for n=4 we have A[1,2,3,4]). Thanks so much for any help/hints! 
March 11th, 2012, 12:59 PM  #2 
Senior Member Joined: Feb 2012 Posts: 628 Thanks: 1  Re: Algorithm question
If all of the integers are in sequence, you can check to see if b is greater than or equal to the sum of all of them. What you're going to need is a way of determining how many ways you can write an integer in the array as a sum of the others. I would start as follows: If b is equal to one of the numbers in the array, then you have already calculated how many ways you can write each integer as a sum of the others, so that is your answer. If b is larger than all of them, then start with the largest number and keep adding the next largest number until the sum is greater than or equal to b.


Tags 
algorithm, question 
Thread Tools  
Display Modes  

Similar Threads  
Thread  Thread Starter  Forum  Replies  Last Post 
GCD new algorithm?  Bogauss  Number Theory  15  March 19th, 2012 08:54 AM 
GCD algorithm  Bogauss  Number Theory  14  March 1st, 2012 03:23 PM 
Prime Numbers Sum Algorithm Question  kokozko  Number Theory  1  November 30th, 2011 07:53 AM 
196Algorithm  skainstein  Number Theory  6  September 15th, 2009 04:39 PM 
What algorithm  mmx64  Algebra  0  July 1st, 2008 11:23 PM 