Please help me...

I am trying to get a hang on this recursion, but I can't manage to write a working recursion-using program. I have this problem:
I have an int n(0-20), and another int k(-1000000, +1000000).
I have n numbers, and I have to combine these numbers, giving them a + or a -, to get k. I have to output the number of different combinations to get k out of these numbers.
e.g.
input

3 6
3 5 2
output
1
explanation: 3+5-2=6, and that is the only way.


help me, plz, the sooner the better, i really need some real examples to understand recursion.
Thx in advance

 

hi!
what can be the maximal value of numbers that you want to combine?
Because for input:
3 6
you can have also
100 100 6

100 - 100 + 6 is also 6

 

ofc, the number can be from 1 to 1000

 

Hi again,
here is my crude attempt to solve this problem (the code is in python and i believe is horribly inneficient):

def combine( n ):
    if n == 0:
        for i in xrange( -10, 11 ):  #increase this to -1000, 1001 if you want
                                            #the number be from <0..1000>
            yield [i, ]
    else:
        for i in combine( n - 1 ):
            for j in combine( 0 ):
                yield j + i

def get_result( n, k ):    
    for tmp in combine( n - 1 ):
        if sum( tmp ) == k:
            yield tmp
        
for r in get_result( 3, 6 ):   #n, k
    print r

Code (markup):

the results are in format

...
[-8, 7, 7]  # -8 + 7 + 7 = 6
[-9, 8, 7]
[-10, 9, 7]
[8, -10, 8]
[7, -9, 8]
...

Code (markup):

total number of results is 295, but there are duplicate results as well, e.g.
-8, 7, 7 and 7, -8, 7 etc.

 

Personally I think the problem is too hard if you're a beginner trying to grasp recursion