credit_suisse.py

"""
Author: Dogu Deniz UGUR (Github: DoguD), 2020
The methodology behind the code has been tried to explained via comments.
All assumptions and notes are also mentioned as comments when necessary.
"""


def get_result(src_list, target, result_list):
    """Note: Although I couldn't find a counter example myself this algorithm may not always return the result with shortest
    number of elements."""

    # Iterate from highest element to the lowest one.
    for e in src_list:
        # Get the highest element which is lower than the target
        if e <= target:
            # Get the index of the element.
            index_e = src_list.index(e)

            # Rearrange target and src_list. And update result list.
            result_list += [e]
            target -= e
            src_list = src_list[index_e + 1:]

            # target == 0 means found n number of elements which adds up to target so return.
            if target == 0:
                return True, result_list
            else:
                # Calls itself with updated list and target
                result, result_list = get_result(src_list, target, result_list)
                if result:
                    return True, result_list
    return False, []


# Get inputs: list and target number (Throws an error if any of the inputs are not integers)
input_list = []
target = 0
"""ASSUMPTION: People will not enter the same element twice. This can mess up the indices of the result list."""
try:
    # List
    n = int(input("Please enter the length of the source list: "))
    for i in range(n):
        element = int(input("Please enter " + str(i) + "th element: "))
        input_list.append(element)

    # Target Number
    target = int(input("Please enter the target number: "))
except:
   print "ERROR: Invalid input."

# Sort the list
sorted_list = sorted(input_list, reverse=True)

# Get the result
result, result_list = get_result(sorted_list, target, [])
# Convert elements in result_list to indices
for i in range(len(result_list)):
    result_list[i] = input_list.index(result_list[i])
# Reverse the result_list (It is from higher indices to lower indices, but in the example it is the other way around)
result_list.reverse()

print 'Solution ' + str(result_list)