Python Array Addition recursion

Question

So I was doing coderbyte's challenge and I have problems with one: ArrayAdditionI, here's the statement of the problem:

''' Using the Python language, have the function ArrayAdditionI(arr) take the array of numbers stored in arr and return the string true if any combination of numbers in the array can be added up to equal the largest number in the array, otherwise return the string false. For example: if arr contains [4, 6, 23, 10, 1, 3] the output should return true because 4 + 6 + 10 + 3 = 23. The array will not be empty, will not contain all the same elements, and may contain negative numbers. '''

Since I couldn't do it, I researched for a solution and I found this:

def countFor(arr, m, s0):
  if len(arr) == 0:
    return False
  a0 = arr[0]
  ar = arr[1:]

  sw = s0 + a0
  if sw == m:
    return True
  if countFor(ar, m, sw):
    return True
  if countFor(ar, m, s0):
    return True
  return False

def ArrayAdditionI(arr): 

  m = max(arr)
  arr.remove(m)
  return str(countFor(arr, m, 0)).lower()

Now, I'm trying to understand what exactly the code does on every loop, I printed out the output for every loop of this list [4, 6, 23, 10, 1, 3]:

Input:  [4, 6, 10, 1, 3] 23 0
a0:  4
ar:  [6, 10, 1, 3]
sw:  4
Input:  [6, 10, 1, 3] 23 4
a0:  6
ar:  [10, 1, 3]
sw:  10
Input:  [10, 1, 3] 23 10
a0:  10
ar:  [1, 3]
sw:  20
Input:  [1, 3] 23 20
a0:  1
ar:  [3]
sw:  21
Input:  [3] 23 21
a0:  3
ar:  []
sw:  24
Input:  [] 23 24
Input:  [] 23 21
Input:  [3] 23 20
a0:  3
ar:  []
sw:  23
True

and I follow and understand what's going on, until the last three loops, I don't what part of the code makes it go from "Input: [] 23 24" to "Input : [] 23 21" to "Input: [3] 23 20".

Alec · Accepted Answer · 2016-07-07 22:55:38Z

2

Alright - here are the calls. Child calls are indented with respect to their parents:

Call countFor([4, 6, 10, 1, 3], 23, 0)
- Call countFor([6, 10, 1, 3], 23, 4) from the first if
- Call countFor([10, 1, 3], 23, 10) from the first if
  - Call countFor([1, 3], 23, 20) from the first if
  - Call countFor([3], 23, 21) from the first if
    - Call countFor([], 23, 24) from the first if
    - Call countFor([], 23, 21) from the second if
  - Call countFor([3], 23, 20) from the second if

Key point is that the second recursive call in countFor is not in an elif - it is an if in its own right, so after we come back up the call-stack, the second recursive call can also happen.

answered Jul 7, 2016 at 22:55

Alec

32.5k7 gold badges73 silver badges120 bronze badges

Sign up to request clarification or add additional context in comments.

Comments

Prune · Accepted Answer · 2016-07-07 23:00:29Z

You haven't traced all of the logic, just the input and update at the top of the routine.

At [] 23 24, let's follow the logic:

if sw == m:

Nope ... that's 24 vs 23 ...

if countFor(ar, m, sw):

This produces your [] 23 24 line. Since the array has 0 elements, the call immediately returns False.

if countFor(ar, m, s0):

This produces your [] 23 21 line. Again, the empty array gets an immediate False.

We fall one more line and return a False to the previous call.

The call that produced this one was the first countFor, calling with

if countFor([3], 23, 21):

where that 21 is the value of sw. We drop to the second call, the one with s0. At this point, s0 is 20, so the call looks like:

if countFor([3], 23, 20):

... and this call sees that 20+3 = 23 = m, so it returns True.

Does that clarify things for you?

vagitus · Accepted Answer · 2023-01-07 15:22:31Z

0

just use the package itertools.combinations:

from itertools import combinations

def arrayChallenge(numbers):
    expected_sum = max(numbers)
    numbers.remove(expected_sum)
    
    result = [seq for i in range(len(numbers), 0, -1)
          for seq in combinations(numbers, i)
          if sum(seq) == expected_sum]

    return len(result) > 0

print(arrayChallenge([4, 6, 23, 10, 1, 3]))

answered Jan 7, 2023 at 15:22

vagitus

4964 silver badges12 bronze badges

Collectives™ on Stack Overflow

Python Array Addition recursion

3 Answers 3

Comments

Comments

Comments

Your Answer

Hot Network Questions

Collectives™ on Stack Overflow

3 Answers 3

Comments

Comments

Comments

Your Answer

Sign up or log in

Post as a guest

Related