Dismiss Notice
Join Physics Forums Today!
The friendliest, high quality science and math community on the planet! Everyone who loves science is here!

Looking for algoritm to the partition problem C

  1. Jan 20, 2009 #1
    write a function called
    Code (Text):

     int partition(int arr[], int size)
    which input an array of integers and decides whether
    it is possible to divide the array into two groups
    so the sums of both the groups will be equal.
    Code (Text):

    for example arr = {1,2,2,3,5,6,1}
    its could be divided into {2,2,6}  and {1,1,3,5} both of their sums is 10
    so they are equal and the function needs to return 1.

    the function must be recursive without loops.
    you are allowed to use only one external recursive function

    and i cant use pointers
    i tied to build a code that sums for ranges
    but the example shows that there could be a possibility
    of two sub sequences mixed with one another
    so the range option is not solving this

  2. jcsd
  3. Jan 25, 2009 #2
    Why does the method have to be recusive? Why can't you use pointers?
  4. Jan 25, 2009 #3


    User Avatar
    Science Advisor
    Homework Helper

    Because CS homework always involves recursion - CS teachers still thinks it's cool.
    Fortunately almost all CS grads remember nothing they have learnt so don't try and use it in the real world.
  5. Jan 25, 2009 #4
    Well then, a little more coded form would help understand the task at hand. For example, since no references or pointers are allowed, how do you intend to retain a calculated value between calls....a member variable or possibly a static or global variable, or are these off limits also?
Share this great discussion with others via Reddit, Google+, Twitter, or Facebook