A recursive problem

This is a discussion on A recursive problem within the C++ Programming forums, part of the General Programming Boards category; Iím having problems with a recursive function that do the following: The function receives an array of numbers (N) and ...

  1. #1
    Registered User
    Join Date
    Oct 2001
    Posts
    3

    A recursive problem

    Iím having problems with a recursive function that do the following:
    The function receives an array of numbers (N) and size.
    The output is 1 if it possible to find cells that their sum equals to size, else it returns 0.
    For example:
    Array= [5 7 2 4 12 8], size=19
    The function will print: 7, 12 or 5,2,4,8, what ever comes up first.

    Thanks,

  2. #2
    Unregistered
    Guest
    It is hard to understand what you are asking. Could you please say what you need the function to do and what exactly you are doing?

  3. #3
    geek SilentStrike's Avatar
    Join Date
    Aug 2001
    Location
    NJ
    Posts
    1,141
    This was an interesting problem, so I decided to solve it . Forgive the C-style pointers everywhere . If you don't understand how it works, ask me.

    Code:
    #include <iostream>
    
    const int LIST_DELIMITER = 0;  // cannot be in the list, else the printing gets messed up
    
    bool sumPossible(int* data, int* answers, int listSize, int target) {
        if (data[0] == target) {
            answers[0] = data[0];
            return true;
        }
    
        for (int i = 1; i < listSize; i++) {
            if (sumPossible(data + i, answers, listSize - i, target)) return true; // data[0] not included in list of answers
            answers[0] = data[0];
            if (sumPossible(data + i, answers + 1, listSize - i, target - data[i])) return true; // data[0] included in list
        }
        return false;
    }
    
    void clearList(int* data, int num) {
        for (int i = 0; i < num; i++) data[i] = LIST_DELIMITER;
    }
    
    void printList(int* data, int num) {
        for (int i = 0; i < num; i++) {
            if (data[i] == LIST_DELIMITER) return;
            std::cout << '\t' << data[i];
        }
    }
    int main(int argc, char *argv[])
    {
        int list[] = {2 , 3 ,4 ,5};
        int answers[] = {LIST_DELIMITER, LIST_DELIMITER, LIST_DELIMITER, LIST_DELIMITER};
        int listSize = 4;
        for (int i = 0; i < 20; i++) {
            bool itWorked = sumPossible(list, answers, listSize, i);
            std::cout << "Target " << i << '\t' << itWorked;
            if (itWorked) {
               printList(answers, listSize);
            }
            clearList(answers, listSize);
            std::cout << std::endl;
        }
        char wait; std::cin >> wait;
        return 0;
    }
    Prove you can code in C++ or C# at TopCoder, referrer rrenaud
    Read my livejournal

Popular pages Recent additions subscribe to a feed

Similar Threads

  1. Recursive Problem.
    By penance in forum C Programming
    Replies: 4
    Last Post: 07-07-2005, 10:16 AM
  2. recursive function problem
    By jk81 in forum C Programming
    Replies: 2
    Last Post: 10-25-2002, 06:02 AM
  3. binary tree problem - help needed
    By sanju in forum C Programming
    Replies: 4
    Last Post: 10-16-2002, 05:18 AM
  4. Problem with a recursive function
    By fofone in forum C Programming
    Replies: 2
    Last Post: 03-07-2002, 07:21 AM
  5. Recursive problem...
    By Unregistered in forum C++ Programming
    Replies: 2
    Last Post: 02-11-2002, 03:20 PM

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21