Thread: Recursive sum in array...

  1. #1
    Registered User
    Join Date
    Oct 2009
    Posts
    7

    Recursive sum in array...

    Hi,

    I have this problem: Given an array, his lenght and a numer (sum to obtain), the alghoritm must return in output all the way to obtain that sum.
    For example:

    8, 11, 8, 7, 7, 6, 5, 4, 3, 2, 2, 1, 1 (where the first 8 is the sum to obtain and 11 is the number of the elements).

    Output:

    8
    7+1
    6+2
    5+3
    5+2+1
    4+3+1
    4+2+2
    4+2+1+1
    3+2+2+1

    The algorithm must be recursive...and the solution must not contain repetition...

    Any idea??

    Thank's...
    Last edited by gandalf215; 10-11-2009 at 08:33 AM.

  2. #2
    spurious conceit MK27's Avatar
    Join Date
    Jul 2008
    Location
    segmentation fault
    Posts
    8,300
    Here's a clue: use a static int in the function to keep track of the number of calls, eg:
    Code:
    int sumArray (int **rayptr, int len, int goal) {
        static int count = 0;
    so the recursion continues until count == (len-1). The last iteration just returns the value at rayptr[count]; the previous iterations return that number plus the next call:
    Code:
    return rayptr[count] + sumArray(rayptr,len,goal);
    [edit] I slightly misunderstood this and thot you were just adding everthing up -- so in fact this function needs no return value, you just have to output rayptr[count]+(8-same) each time.[/edit]
    Last edited by MK27; 10-11-2009 at 12:48 PM.
    C programming resources:
    GNU C Function and Macro Index -- glibc reference manual
    The C Book -- nice online learner guide
    Current ISO draft standard
    CCAN -- new CPAN like open source library repository
    3 (different) GNU debugger tutorials: #1 -- #2 -- #3
    cpwiki -- our wiki on sourceforge

  3. #3
    Algorithm Dissector iMalc's Avatar
    Join Date
    Dec 2005
    Location
    New Zealand
    Posts
    6,318
    Clue? That's more of a cop-out!
    I stongly advise against using a static. It will not be intended for you to do so and you would not learn as much about what you are supposed to be learning.

  4. #4
    ATH0 quzah's Avatar
    Join Date
    Oct 2001
    Posts
    14,826
    What are you actually trying to do? You're not summing up your array, so what it is you're really doing? Factorial? Or what? Because all your example shows is a bunch of number combinations that end up equaling 8.

    What does that have to do with your array? You're either not explaining what you need, or you're not understanding what you really need.


    Quzah.
    Hope is the first step on the road to disappointment.

  5. #5
    Registered User
    Join Date
    Oct 2009
    Posts
    7
    I try to explaine better: :-D

    "Given a specified total t and a list of n integers, find all distinct sums using numbers from the list that add up to t. For example, if t = 4, n = 6, and the list is [4, 3, 2, 2, 1, 1], then there are four different sums that equal 4: 4, 3+1, 2+2, and 2+1+1. (A number can be used within a sum as many times as it appears in the list, and a single number counts as a sum.)

    Input
    The input file will contain one or more test cases, one per line. Each test case contains t, the total, followed by n, the number of integers in the list, followed by n integers $x_1, \dots, x_n$. If n = 0 it signals the end of the input; otherwise, t will be a positive integer less than 1000, n will be an integer between 1 and 12 (inclusive), and $x_1, \dots, x_n$ will be positive integers less than 100. All numbers will be separated by exactly one space. The numbers in each list appear in nonincreasing order, and there may be repetitions.

    Output
    For each test case, first output a line containing `Sums of ', the total, and a colon. Then output each sum, one per line; if there are no sums, output the line `NONE'. The numbers within each sum must appear in nonincreasing order. A number may be repeated in the sum as many times as it was repeated in the original list. The sums themselves must be sorted in decreasing order based on the numbers appearing in the sum. In other words, the sums must be sorted by their first number; sums with the same first number must be sorted by their second number; sums with the same first two numbers must be sorted by their third number; and so on. Within each test case, all sums must be distinct; the same sum cannot appear twice. "

  6. #6
    ATH0 quzah's Avatar
    Join Date
    Oct 2001
    Posts
    14,826
    Ok, so given an array, and two values (what you're looking for, and the length of the array), run through the array and look for things that add up to what you're trying to find? Gotcha.

    Ok, so where's your attempt?


    Quzah.
    Hope is the first step on the road to disappointment.

  7. #7
    Registered User
    Join Date
    Oct 2009
    Posts
    7
    i have done an iterative algorithm, but i must develop a recursive algorithm and i'm not very expert in that...

  8. #8
    Registered User
    Join Date
    Sep 2006
    Posts
    8,868
    Let's see. First thing would be to sort the numbers, and then remove all the duplicates (like 1, 2 and 7), from the given numbers. Second, compare the numbers to the target you're trying to match. Obviously, 11 can be removed (and any number greater than 8), because it (they), can play no part in a solution.

    Target: 8

    Original numbers:
    11, 8, 7, 7, 6, 5, 4, 3, 2, 2, 1, 1

    Numbers After Filtering:
    1,2,3,4,5,6,7,8

    Now you're ready to work on your recursive function or functions.

    (base == 0), add one number:
    1
    2
    3
    4
    5
    6
    7
    8

    base == 1, add one number:
    1+2
    1+3
    1+4
    1+5
    1+6
    1+7
    1+8


    (2+1) Wrong. Only work with numbers to your right. Eliminates duplicates
    2+3
    2+4
    2+5
    2+6
    2+7 When the sum > target, stop working with that number


    Now work with a base of two numbers: (and you always add one new number to the base)

    1+2+3
    1+2+4
    1+2+5
    1+2+6 Sum > target, so stop with the two's

    1+2+3+4 Start with the 3's for a base (and always adding one more to the base)
    Since the first sum > the target, you can stop all further combinations. They will all be greater than the target.

    I wouldn't advise you on the recursive function. You need to sort that out, at least a bit, on your own. Post up what you have, if you get stuck.

    I hope the above clarifies some of what you need to do, however.
    Last edited by Adak; 10-11-2009 at 01:27 PM.

  9. #9
    ATH0 quzah's Avatar
    Join Date
    Oct 2001
    Posts
    14,826
    Except you wouldn't filter out dupes. Ie:

    Find sum of 8 in: 7,6,5,4,4,3,3,2,2,2,1,1
    Spits out stuff like...
    7+1
    6+2
    6+1+1
    5+3
    5+2+1
    4+4
    4+3+1
    4+2+2
    4+2+1+1
    ...

    Also, I assume that the list isn't actually guaranteed to be sorted.


    Quzah.
    Hope is the first step on the road to disappointment.

  10. #10
    spurious conceit MK27's Avatar
    Join Date
    Jul 2008
    Location
    segmentation fault
    Posts
    8,300
    Quote Originally Posted by gandalf215 View Post
    i have done an iterative algorithm, but i must develop a recursive algorithm and i'm not very expert in that...
    By "inexpert" you mean you have used recursion before a little bit, or not at all?
    Was anything I said in post #2 helpful (I suppose not )? What have you tried so far (post some code)?

    The simplest illustration of recursion is a "factorial" function:
    Code:
    int factorial (int n) {
            if (n==1) return n;
            return n*factorial(n-1);
    }
    The factorial of 6 is 720:
    1x2x3x4x5x6=720
    Can you see how this function will return that?

    Obviously your assignment is considerably more complex tho! Can I ask what this part is supposed to mean:

    Quote Originally Posted by gandalf215 View Post
    followed by n integers $x_1, \dots, x_n$. If n = 0 it signals the end of the input; otherwise, t will be a positive integer less than 1000, n will be an integer between 1 and 12 (inclusive), and $x_1, \dots, x_n$ will be positive integers less than 100. All numbers will be separated by exactly one space. The numbers in each list appear in nonincreasing order, and there may be repetitions.
    Does this vaguely imply each "number" is a set of three? What is the point of referring to "$x_1, \dots, x_n$"?

    Best of all would be if you had a sample of this potential input.
    Last edited by MK27; 10-11-2009 at 01:42 PM.
    C programming resources:
    GNU C Function and Macro Index -- glibc reference manual
    The C Book -- nice online learner guide
    Current ISO draft standard
    CCAN -- new CPAN like open source library repository
    3 (different) GNU debugger tutorials: #1 -- #2 -- #3
    cpwiki -- our wiki on sourceforge

  11. #11
    Registered User
    Join Date
    Oct 2009
    Posts
    7
    Quote Originally Posted by MK27 View Post
    By "inexpert" you mean you have used recursion before a little bit, or not at all?
    i know theorical bases of recursion, but i never had programmed nothing using this programming method...

    Quote Originally Posted by MK27 View Post
    The factorial of 6 is 720:
    1x2x3x4x5x6=720
    Can you see how this function will return that?
    yes...the example of factorial function is the "classical" explained in the books...

  12. #12
    Registered User
    Join Date
    Oct 2009
    Posts
    7
    Quote Originally Posted by quzah View Post

    Also, I assume that the list isn't actually guaranteed to be sorted.

    Quzah.
    No, the list is guaranteed to be sorted!

  13. #13
    Registered User
    Join Date
    Sep 2006
    Posts
    8,868
    Quzah, of course there would be no duplicates, and sorting was mentioned in my post (although now I see Gandalf says the list is already sorted).

    I have a program that does this exact job, so it works. Unfortunately, it's iterative, not recursive. Also, I believe Gandalf needs to work with the recursion part, and his program in general, and post his effort, at least.

  14. #14
    ATH0 quzah's Avatar
    Join Date
    Oct 2001
    Posts
    14,826
    Quote Originally Posted by Adak View Post
    Quzah, of course there would be no duplicates
    Oh really? Read the OP:
    Output:

    8
    7+1
    6+2
    5+3
    5+2+1
    4+3+1
    4+2+2
    4+2+1+1
    3+2+2+1
    So 2+2 means there isn't more than one 2? And 1+1 means there isn't more than one one?


    Quzah.
    Hope is the first step on the road to disappointment.

  15. #15
    Registered User
    Join Date
    Sep 2006
    Posts
    8,868
    Quote Originally Posted by quzah View Post
    Oh really? Read the OP:So 2+2 means there isn't more than one 2? And 1+1 means there isn't more than one one?


    Quzah.
    Well, of course, I thought you were addressing your comments to my post right before yours. Naturally, the duplicate numbers have to be filtered out.

    The OP doesn't know WTF he's posting. Isn't that a given?

Popular pages Recent additions subscribe to a feed

Similar Threads

  1. Returning an object with a dynamic pointer
    By maxsthekat in forum C++ Programming
    Replies: 11
    Last Post: 09-16-2009, 01:52 PM
  2. Replies: 2
    Last Post: 07-11-2008, 07:39 AM
  3. [question]Analyzing data in a two-dimensional array
    By burbose in forum C Programming
    Replies: 2
    Last Post: 06-13-2005, 07:31 AM
  4. Class Template Trouble
    By pliang in forum C++ Programming
    Replies: 4
    Last Post: 04-21-2005, 04:15 AM
  5. Help with an Array
    By omalleys in forum C Programming
    Replies: 1
    Last Post: 07-01-2002, 08:31 AM