recursion on each element of array

Question

I have an integer S and a collection A of integers. I need to find a set of integers from the collection where the sum of those integers is equal to S. It could be 1 integer or 50 - it doesn't matter.

I'm trying to do this like this:

I have an array res and an array grp

res starts with [0], grp is the initially given collection, and S is the sum we're trying to find, S is global

my function takes (res, grp)

I want to do this : (and example)

-

and stop when the sum of the res elements is equal to S

but I suck with recursion and I have no idea what I should be doing

this is my code

S = 7
grp = [0,5,6,4,3]

def sumFinder(res,grp):
    if grp == []:
        return grp #in case no pair was found [] is returned 
    if sum(res) == S:
        return res
    for i in range (0,len(grp)):
        print(res)
        print(grp[i])
        res += [grp[i]]
        newgrp = grp[:i]
        newgrp += grp[i+1:]
        return sumFinder(res,newgrp)

 print(sumFinder([0],grp))

UPDATE:

thank you everyone for you answers thank you englealuze for giving me a beter idea about approaching the problem thanks o you i got to this:

1 - this is for finding the first combination and returning it (this was my goal)

grp = [1,0,1,0,1,2,6,2,3,5,6,7,8,9,2,1,1,9,6,7,4,1,2,3,2,2]
S = 55
grps = []

def findCombination(comb,grp):
    for i in range (0,len(grp)):
        comb += [grp[i]]
        newgrp = grp[:i]
        newgrp += grp[i+1:]

        if sum(comb) == S:
            return comb

        if newgrp not in grps:
            grps.append(newgrp)
            res = findCombination([],newgrp)
            if res != None:
                return res

print(findCombination([],grp))

2- this is for finding all the combinations: (this is the problem englealuze talked about, but i didn't understand his method that well even though it seems better)

grp = [1,0,1,1,9,6,7,4,1,2,3,2,2]
S = 12
grps = []
combinations = []

def findAllCombinations(comb,grp):
    global combinations
    for i in range (0,len(grp)):
        comb += [grp[i]]
        newgrp = grp
        newgrp = grp[:i]
        newgrp += grp[i+1:]

        if sum(comb) == S and tuple(comb) not in combinations:
            combinations.append(tuple(comb))

        if newgrp not in grps:
            grps.append(newgrp)
            findAllCombinations([],newgrp)

findAllCombinations([],grp)
print(combinations)

my only problem now is that when S > 50 (in the first one), it takes longer to find the answer

what advice could you guys give me to improve both algorithms?

Answer 1

In stead of just providing code, I will show you how to think about this problem and how to tackle this type of problems in a general sense.

First, let us rephrase your question. In fact what you want is for a given set of numbers, find the combinations within the set which fulfill certain condition. So, you can decompose your question into 2 distinct steps.

1. Find all combinations of your set
2. Filter out the combinations that fulfill certain conditions

Let us think about how to solve the first task recursively. Remember, if a problem can be solved in a recursive way, it generally means there are some recursive patterns within your data and it usually can be solved in a very simple and clear way. If you end up with a messy recursive solution, it pretty much means you are in a wrong direction.

Let us see the pattern of your data first. If you have a very small set (1, 2), then the combinations out of this set are

1
2
1, 2

Let us increase one member to the set, (1, 2, 3). For this bigger set, all combiantions are

1       | 1, 3
2       | 2, 3
1, 2    | 1, 2, 3
        | 3

Let us look at even bigger set (1, 2, 3, 4). The possible combinations are

1       1, 3       | 1, 3, 4
2       2, 3       | 2, 3, 4
1, 2    1, 2, 3    | 1, 2, 3, 4
        3          | 3, 4
                   | 4

Now you see something interesting, the combinations of one bigger set is the combinations of the smaller set plus the additional element appending to every previous combination and plus the additional element itself.

Assume you already got the solution of all combinations of set with certain size, the solution of a bigger set can be derived from this solution. This naturally forms a recursion. You can translate this plain English directly to a recursive code as below

# assume you have got all combinations of a smaller set -> combinations(smaller(L))
# the solution of your bigger set can be directly derived from it with known new element
def combinations(L):
    if L == []:
        return []
    else:
        return next_solution(combinations(smaller(L)), newitem(L))

Notice how we decompose out task of solving a larger problem to solving smaller problems. You need the helper functions as below

# in your case a smaller set is just the new set drop one element
def smaller(L):
    return L[1:]

# the new element would be the first element of new set
define newitem(L):
    return L[0]

# to derive the new solution from previous combinations, you need three parts
# 1. all the previous combinations -> L
# 2. new item appending to each previous combination -> [i + [newelement] for i in L]
# 3. the new item itself [[newelement]]
def next_solution(L, newelement):
    return L + [i + [newelement] for i in L] + [[newelement]]

Now we know how to get all combinations out of a set. Then to filter them, you cannot just insert the filter directly into your recursive steps, since we rely on our previous solution to build up the result list recursively. The simple way is to filter the list while we obtain the full result of all combinations.

You will end up with a solution as this.

def smaller(L):
  return L[1:]

def newitem(L):
  return L[0]

def next_solution(L, newelement):
  return L + [i + [newelement] for i in L] + [[newelement]]

def filtersum(L, N, f=sum):
  return list(filter(lambda x: f(x)==N, L))

def combinations(L):
  if L == []:
    return []
  else:
    return next_solution(combinations(smaller(L)), newitem(L))

def filter_combinations(L, N, f=filtersum):
  return f(combinations(L), N)

print(filter_combinations([0,5,6,4,3], 7))
# -> [[3, 4], [3, 4, 0]]

You can save some computations by filter out in each recursive call the combinations with sum bigger than your defined value, such as

def combinations(L):
  if L == []:
    return []
  else:
    return next_solution(list(filter(lambda x: sum(x) <=5, combinations(smaller(L)))), newitem(L))

print(combinations([1,2,3,4]))
# -> [[4], [3], [3, 2], [2], [4, 1], [3, 1], [3, 2, 1], [2, 1], [1]]

In fact there will be different ways to do recursion, depends on the way how you decompose your problem to smaller problems. There existed some smarter ways, but the approach I showed above is a typical and general approach for solving this type of problems.

I have example of solving other problems with this way

Python: combinations of map tuples

Answer 2

Below codes work (remove 'directly return' in the loop, changed to conditional 'return').

But I don't think it is a good solution. You need to improve your algorithm.

PS: This codes also will only return one match instead of all.

S = 7
grp = [0,3,6,4,6]

result = []

def sumFinder(res,grp, result):
    for i in range (0,len(grp)):
        temp = list(res) #clone res instead of direct-reference
        if grp == [] or not temp:
            return grp #in case no pair was found [] is returned
        if sum(temp) == S:
            result.append(tuple(temp))
            return temp
        temp.append(grp[i])
        newgrp = grp[:i] + grp[i+1:]
        sumFinder(list(temp),newgrp, result)

sumFinder([0], grp, result)
print result

Test Cases:

S = 7
grp = [0,3,6,4,6]
result = [(0, 0, 3, 4), (0, 0, 4, 3), (0, 3, 0, 4), (0, 3, 4), (0, 4, 0, 3), (0, 4, 3)]
[Finished in 0.823s]

Answer 3

Can you let me know where did you find this problem? I love to solve this type of problem, Bdw here is my approach:

a=[[[0],[0,5,6,4,3]]]

s=7

def recursive_approach(array_a):
    print(array_a)
    sub=[]
    for mm in array_a:
        array_1 = mm[0]
        array_2 = mm[1]
        if sum(array_2)==s:
            return "result is",array_2
        else:
            track = []
            for i in range(len(array_2)):
                c = array_2[:]
                del c[i]

                track.append([array_1 + [array_2[i]], c])
            sub.append(track)
    print(sub)
    return recursive_approach(sub[0])





print(recursive_approach(a))

output:

[[[0], [0, 5, 6, 4, 3]]]
[[[[0, 0], [5, 6, 4, 3]], [[0, 5], [0, 6, 4, 3]], [[0, 6], [0, 5, 4, 3]], [[0, 4], [0, 5, 6, 3]], [[0, 3], [0, 5, 6, 4]]]]
[[[0, 0], [5, 6, 4, 3]], [[0, 5], [0, 6, 4, 3]], [[0, 6], [0, 5, 4, 3]], [[0, 4], [0, 5, 6, 3]], [[0, 3], [0, 5, 6, 4]]]
[[[[0, 0, 5], [6, 4, 3]], [[0, 0, 6], [5, 4, 3]], [[0, 0, 4], [5, 6, 3]], [[0, 0, 3], [5, 6, 4]]], [[[0, 5, 0], [6, 4, 3]], [[0, 5, 6], [0, 4, 3]], [[0, 5, 4], [0, 6, 3]], [[0, 5, 3], [0, 6, 4]]], [[[0, 6, 0], [5, 4, 3]], [[0, 6, 5], [0, 4, 3]], [[0, 6, 4], [0, 5, 3]], [[0, 6, 3], [0, 5, 4]]], [[[0, 4, 0], [5, 6, 3]], [[0, 4, 5], [0, 6, 3]], [[0, 4, 6], [0, 5, 3]], [[0, 4, 3], [0, 5, 6]]], [[[0, 3, 0], [5, 6, 4]], [[0, 3, 5], [0, 6, 4]], [[0, 3, 6], [0, 5, 4]], [[0, 3, 4], [0, 5, 6]]]]
[[[0, 0, 5], [6, 4, 3]], [[0, 0, 6], [5, 4, 3]], [[0, 0, 4], [5, 6, 3]], [[0, 0, 3], [5, 6, 4]]]
[[[[0, 0, 5, 6], [4, 3]], [[0, 0, 5, 4], [6, 3]], [[0, 0, 5, 3], [6, 4]]], [[[0, 0, 6, 5], [4, 3]], [[0, 0, 6, 4], [5, 3]], [[0, 0, 6, 3], [5, 4]]], [[[0, 0, 4, 5], [6, 3]], [[0, 0, 4, 6], [5, 3]], [[0, 0, 4, 3], [5, 6]]], [[[0, 0, 3, 5], [6, 4]], [[0, 0, 3, 6], [5, 4]], [[0, 0, 3, 4], [5, 6]]]]
[[[0, 0, 5, 6], [4, 3]], [[0, 0, 5, 4], [6, 3]], [[0, 0, 5, 3], [6, 4]]]
('result is', [4, 3])