0

My goal is to write a function that takes in a list of integers - ints - and a sum goal - s - and returns a list of the first two integers in the list that add up to s in the order they appear in the list from left to right. I have the function print to console for every iteration and everything looks good except it always returns None and I have no idea how. My code:

def sum_pairs(ints, s, a=0, b=1):
    if a == len(ints)-1 or b > 666:
        return None
    if b < len(ints):
        print(s, a,b,[ints[a],ints[b]], ints[a] + ints[b])
        if ints[a] + ints[b] == s:
            x = ints[a]
            y = ints[b]
            print([x,y], type([x,y]), [x,y] is None)
            return [x, y]
        else: 
            sum_pairs(ints, s, a, b=b+1)
    else:
        sum_pairs(ints, s, a=a+1, b=a+2)

I even checked if [x,y] is None in the step before the return statement and it always returns False yet somehow the function still returns None. Can somebody fill me in? I'm new to recursion so maybe the problem lies there.

Thomas Upton
  • 1,853
  • 12
  • 22
Aaron Bergfeld
  • 1
  • 5
    Your function is missing `return` statements in half of the cases. – Klaus D. Mar 30 '20 at 14:38
  • Put return in front of the recursive calls: `return sum_pairs(ints, s, a, b=b+1)`, and `return sum_pairs(ints, s, a=a+1, b=a+2)`. Also, this algorithm is easier to formulate as an iterative, not recursive – Alex Sveshnikov Mar 30 '20 at 14:40
  • Klaus has the correct answer. Unrelated, I highly recommend using a debugger. – NadavS Mar 30 '20 at 14:45

1 Answers1

0

I would start writing a generic combinations function which generates combinations of a specified size -

def combinations(items, size):
  if size == 0:
    yield ()
  elif not items:
    return
  else:
    head, *tail = items
    for p in combinations(tail, size - 1):
      yield (head, *p)
    yield from combinations(tail, size)

We're relying on Python's generators which lazily produce the output. We can use list to get all of the results -

data = [ 1, 2, 3, 4, 5, 6, 7, 8 ]

list(combinations(data, 2))
# [ (1, 2), (1, 3), (1, 4), (1, 5), (1, 6), (1, 7), (1, 8), (2, 3),
#   (2, 4), (2, 5), (2, 6), (2, 7), (2, 8), (3, 4), (3, 5), (3, 6),
#   (3, 7), (3, 8), (4, 5), (4, 6), (4, 7), (4, 8), (5, 6), (5, 7),
#   (5, 8), (6, 7), (6, 8), (7, 8) ]

It can easily generate combinations of other sizes, and the input iterable can contain elements of any type -

list(combinations("abcd", 3)))
# [ ('a', 'b', 'c'), ('a', 'b', 'd'),
#   ('a', 'c', 'd'), ('b', 'c', 'd') ]

By writing combinations as a standalone function we detangle the concerns of our program. As a result sum_pairs is easy to write and test. We pass 2 as the size argument because we want to generate pairs (of two numbers) -

def sum_pairs(ints, goal):
  for p in combinations(ints, 2): # <-- use combinations
    if sum(p) == goal:
      return p
  return None                     # <-- don't forget unsolvable case


print(sum_pairs(data, 13))
# (5, 8)

Because we are using Python's generators, sum_pairs will return immediately after finding an answer. This short-circuit behaviour means no unnecessary combinations or iterations are wasted.

When given an unreachable goal, sum_pairs will return None -

print(sum_pairs(data, 99))
# None

A small modification demonstrates the effectiveness of our combinations generic. In this program, any_sum will find a combination of any size that sums to our expected goal -

def any_sum(ints, goal):
  for size in range(len(ints)):
    for p in combinations(ints, size + 1):
      if sum(p) == goal:
        return p
  return None

While this is not the most efficient implementation of any_sum, it does show how combinations can be reused without introducing new complexity -

print(any_sum(data, 17))
# (2, 7, 8)

print(any_sum(data, 25))
# (4, 6, 7, 8)

print(any_sum(data, 33))
# (3, 4, 5, 6, 7, 8)

print(any_sum(data, 99))
# None
Guest
  • 1
  • 1