The goal of the problem is to reach a True or False conclusion. If n can be made from a combination of numbers in an array then True, if not then False.

Example: n = 8 , arr = [2, 4], expected result is True because 4 4 = 8 or 2 2 2 2 = 8 or 2 2 4 = 8 and so on. The result would be false if n = 5 and arr= [2, 4]. No combination of those numbers will give 5 therefore the result would be false. I have started out but am running into difficulty, the code I have is below

def sum_exists(n, i, p_list=[]):

#n = the number chosen 
#i = the sum of the array
#p_list = the array of numbers to be chosen from

#below are my base cases upon which the recursion depends

  #if the sum is 0 return true as there is nothing that needs to be added
  if (i == 0): 
    return True

  # if the number chosen is 0 and the sum is not equal to 0 then return false as the statement 
    cannot be true 
  # and both individual statements need to be true for the entire statement to be true
  if (n == 0 and i != 0):
    return False  

  #if the last number is the array is greater than the sum 
  #we cannot add it to the sum as if would be greater than n. Therefore we ignore
  if (p_list[n-1] > i):
    return sum_exists(n-1, i, p_list)

  #checking to see if i can be obtained by removing the last number of p_list or including it
  else:
    return sum_exists(n-1, i, p_list) or sum_exists(n-1, i-p_list[n-1], p_list)

#driving function
p_list = [2, 3, 5]
i = 17
n = len(p_list)
if (sum_exists(n, i, p_list) == True):
  print('True')
else:
  print('False')

The issues I'm having

1. I cannot perform repetitions of the array Ex n = 8, p_list = [2 4] gives False, whereas it should give true as multiple combinations can be done
2. How do I get away from having to implement a driver code using print?
3. How can I list multiple arrays for multiple n's in the same code?

Not expecting a solution, just some guidance

CodePudding user response：

One way to accomplish this:

def sum_exists(n, p_list=[], current_sum=0, sum_track = []):
    if current_sum>n:
        return False
    
    elif current_sum == n:
        print(sum_track)
        return True
    
    else:
        new_sums = [current_sum   x for x in p_list]

        truth_list = [sum_exists(n, p_list, s, sum_track [s]) for s in new_sums]
        #Printing the line below may help you understand what's going on.
        #print("Truth list: ", truth_list, "New sums:",new_sums)

        return any(truth_list)



print(sum_exists(17, [2,3,5]))

Explanation: I got rid of the i parameter you have because I approached the problem in a different way. I just have:

• n, the target number
• p_list, the list of possibilities we can choose from to add (with replacement)
• current_sum, which determines when to end the recursion
• sum_track, an array which shows us how we got to the final number we want (this is not necessary, but just to show you how we got to the true or false conclusion).

The logic of the code is simple. The new_sums list indicates the set of new possibilities to be considered as we keep adding. If the current_sum (which is one of the elements in new_sum) is greater than the desired number, we return False, if not, we return True.

The truth list is where the recursion occurs. Finally, the any() statement allows us to see if at least one of the returned values in the truth list is true, if it is, then we know that we can sum up to the target number with the elements in the list.

I am not sure if this is the most efficient way to do things, but I think it is illustrative.

Output:

[2, 4, 6, 8, 10, 12, 14, 17]
[2, 4, 6, 8, 10, 12, 15, 17]
[2, 4, 6, 8, 10, 12, 17]
[2, 4, 6, 8, 10, 13, 15, 17]
[2, 4, 6, 8, 10, 15, 17]
[2, 4, 6, 8, 11, 13, 15, 17]
...
[5, 10, 12, 14, 17]
[5, 10, 12, 15, 17]
[5, 10, 12, 17]
[5, 10, 13, 15, 17]
[5, 10, 15, 17]
True

(You can tell which number is being added by subtracting two consecutive numbers).

CodePudding user response：

You can write a recursive function for one n/arr. Simply call it multiple times if you have many test cases to check (or write a separate function to go through the test cases, which doesn't require recursion):

def canSum(n,arr):
    if not n or not arr:   # zero always works, an empty arr, never does
        return n == 0
    m    = max(arr)        # start with larger numbers to maximize speed
    rest = arr.copy()      # recursion will use rest of numbers
    rest.remove(m)
    for use in reversed(range(0,n 1,m)): # multiples from large to small
        if canSum(n-use,rest):           # recurse with rest
            return True
    return False

output:

print(canSum(8,[2,4]))      # True
print(canSum(15,[2,4]))     # False
print(canSum(18,[3,4]))     # True
print(canSum(12,[3,8,5]))   # True

You can also make a non-recursive solution using a set of reachable values that you progress applying all numbers to all previous results:

def canSum(n,arr):
    reachable = set(arr)
    while reachable and n not in reachable:
        reachable = {r a for r in reachable for a in arr if (r a)<=n}
    return n in reachable

Note that these solutions only work if all numbers in arr are positive