'''simple docstring'''




import math






def __lowerCAmelCase					(				UpperCamelCase__							,    UpperCamelCase__ = 0							,    UpperCamelCase__ = 0							)      ->       list:
    __lowerCamelCase            =    end or len(UpperCamelCase__							)
    for i in range(UpperCamelCase__							,    UpperCamelCase__							):
        __lowerCamelCase            =    i
        __lowerCamelCase            =    array[i]
        while temp_index != start and temp_index_value < array[temp_index - 1]:
            __lowerCamelCase            =    array[temp_index - 1]
            temp_index -= 1
        __lowerCamelCase            =    temp_index_value
    return array






def __lowerCAmelCase					(				UpperCamelCase__							,    UpperCamelCase__							,    UpperCamelCase__							)      ->       None:  # Max Heap
    __lowerCamelCase            =    index
    __lowerCamelCase            =    2 * index + 1  # Left Node
    __lowerCamelCase            =    2 * index + 2  # Right Node

    if left_index < heap_size and array[largest] < array[left_index]:
        __lowerCamelCase            =    left_index

    if right_index < heap_size and array[largest] < array[right_index]:
        __lowerCamelCase            =    right_index

    if largest != index:
        __lowerCamelCase      ,    __lowerCamelCase            =    array[largest], array[index]
        heapify(UpperCamelCase__							,    UpperCamelCase__							,    UpperCamelCase__							)






def __lowerCAmelCase					(				UpperCamelCase__							)      ->       list:
    __lowerCamelCase            =    len(UpperCamelCase__							)

    for i in range(n // 2							,    -1							,    -1							):
        heapify(UpperCamelCase__							,    UpperCamelCase__							,    UpperCamelCase__							)

    for i in range(n - 1							,    0							,    -1							):
        __lowerCamelCase      ,    __lowerCamelCase            =    array[0], array[i]
        heapify(UpperCamelCase__							,    0							,    UpperCamelCase__							)

    return array






def __lowerCAmelCase					(				UpperCamelCase__							,    UpperCamelCase__							,    UpperCamelCase__							,    UpperCamelCase__							)      ->       int:
    if (array[first_index] > array[middle_index]) != (
        array[first_index] > array[last_index]
    ):
        return array[first_index]
    elif (array[middle_index] > array[first_index]) != (
        array[middle_index] > array[last_index]
    ):
        return array[middle_index]
    else:
        return array[last_index]






def __lowerCAmelCase					(				UpperCamelCase__							,    UpperCamelCase__							,    UpperCamelCase__							,    UpperCamelCase__							)      ->       int:
    __lowerCamelCase            =    low
    __lowerCamelCase            =    high
    while True:
        while array[i] < pivot:
            i += 1
        j -= 1
        while pivot < array[j]:
            j -= 1
        if i >= j:
            return i
        __lowerCamelCase      ,    __lowerCamelCase            =    array[j], array[i]
        i += 1






def __lowerCAmelCase					(				UpperCamelCase__							)      ->       list:
    if len(UpperCamelCase__							) == 0:
        return array
    __lowerCamelCase            =    2 * math.ceil(math.loga(len(UpperCamelCase__							)							)							)
    __lowerCamelCase            =    16
    return intro_sort(UpperCamelCase__							,    0							,    len(UpperCamelCase__							)							,    UpperCamelCase__							,    UpperCamelCase__							)






def __lowerCAmelCase					(				UpperCamelCase__							,    UpperCamelCase__							,    UpperCamelCase__							,    UpperCamelCase__							,    UpperCamelCase__							)      ->       list:
    while end - start > size_threshold:
        if max_depth == 0:
            return heap_sort(UpperCamelCase__							)
        max_depth -= 1
        __lowerCamelCase            =    median_of_a(UpperCamelCase__							,    UpperCamelCase__							,    start + ((end - start) // 2) + 1							,    end - 1							)
        __lowerCamelCase            =    partition(UpperCamelCase__							,    UpperCamelCase__							,    UpperCamelCase__							,    UpperCamelCase__							)
        intro_sort(UpperCamelCase__							,    UpperCamelCase__							,    UpperCamelCase__							,    UpperCamelCase__							,    UpperCamelCase__							)
        __lowerCamelCase            =    p
    return insertion_sort(UpperCamelCase__							,    UpperCamelCase__							,    UpperCamelCase__							)


if __name__ == "__main__":
  import doctest

  doctest.testmod()

  __UpperCAmelCase					=input("Enter numbers separated by a comma : ").strip()
  __UpperCAmelCase					=[float(item) for item in user_input.split(",")]
  print(sort(unsorted))

'''simple docstring'''




def __lowerCAmelCase					(				UpperCamelCase__							,    UpperCamelCase__							,    UpperCamelCase__							)      ->       int:

    def count_of_possible_combinations(UpperCamelCase__							) -> int:
        if target < 0:
            return 0
        if target == 0:
            return 1
        return sum(count_of_possible_combinations(target - item							) for item in array							)

    return count_of_possible_combinations(UpperCamelCase__							)






def __lowerCAmelCase					(				UpperCamelCase__							,    UpperCamelCase__							,    UpperCamelCase__							)      ->       int:

    def count_of_possible_combinations_with_dp_array(
        UpperCamelCase__							,    UpperCamelCase__							) -> int:
        if target < 0:
            return 0
        if target == 0:
            return 1
        if dp_array[target] != -1:
            return dp_array[target]
        __lowerCamelCase            =    sum(
            count_of_possible_combinations_with_dp_array(target - item							,    UpperCamelCase__							)
            for item in array							)
        __lowerCamelCase            =    answer
        return answer

    __lowerCamelCase            =    [-1] * (target + 1)
    return count_of_possible_combinations_with_dp_array(UpperCamelCase__							,    UpperCamelCase__							)






def __lowerCAmelCase					(				UpperCamelCase__							,    UpperCamelCase__							,    UpperCamelCase__							)      ->       int:
    __lowerCamelCase            =    [0] * (target + 1)
    __lowerCamelCase            =    1

    for i in range(1							,    target + 1							):
        for j in range(UpperCamelCase__							):
            if i - array[j] >= 0:
                dp_array[i] += dp_array[i - array[j]]

    return dp_array[target]


if __name__ == "__main__":
  import doctest

  doctest.testmod()
  __UpperCAmelCase					=3
  __UpperCAmelCase					=5
  __UpperCAmelCase					=[1, 2, 5]
  print(combination_sum_iv(n, array, target))
