



'''simple docstring'''




def        lowerCAmelCase_     (			_lowerCamelCase:     int ,   _lowerCamelCase:     list[int] ,   _lowerCamelCase:     int      ):

		def count_of_possible_combinations(_lowerCamelCase:     int      ) -> 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(_lowerCamelCase      )


def        lowerCAmelCase_     (			_lowerCamelCase:     int ,   _lowerCamelCase:     list[int] ,   _lowerCamelCase:     int      ):

		def count_of_possible_combinations_with_dp_array(
		    _lowerCamelCase:     int ,   _lowerCamelCase:     list[int]      ) -> int:
				if target < 0:
						return 0
				if target == 0:
						return 1
				if dp_array[target] != -1:
						return dp_array[target]
				__SCREAMING_SNAKE_CASE :	Tuple					 =	sum(
				    count_of_possible_combinations_with_dp_array(target - item ,   _lowerCamelCase      )
				    for item in array      )
				__SCREAMING_SNAKE_CASE :	str					 =	answer
				return answer

		__SCREAMING_SNAKE_CASE :	List[Any]					 =	[-1] * (target + 1)
		return count_of_possible_combinations_with_dp_array(_lowerCamelCase ,   _lowerCamelCase      )


def        lowerCAmelCase_     (			_lowerCamelCase:     int ,   _lowerCamelCase:     list[int] ,   _lowerCamelCase:     int      ):
		__SCREAMING_SNAKE_CASE :	List[str]					 =	[0] * (target + 1)
		__SCREAMING_SNAKE_CASE :	Tuple					 =	1

		for i in range(1 ,   target + 1      ):
				for j in range(_lowerCamelCase      ):
						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__ :			str												=				3
		UpperCamelCase__ :			List[Any]												=				5
		UpperCamelCase__ :			Any												=				[1, 2, 5]
		print(combination_sum_iv(n, array, target))




'''simple docstring'''




from ..utils import DummyObject, requires_backends






class 		_UpperCamelCase						(							metaclass=lowerCamelCase__					):


			'''simple docstring'''

			_A   :	Optional[int]    					=	['''onnx''']

			def __init__(							self  :				List[str]							,  *lowerCAmelCase__  :				Optional[int]							,  **lowerCAmelCase__  :				List[Any]		):





					"""simple docstring"""






					requires_backends(self							,  ["""onnx"""]		)

			@classmethod
			def UpperCamelCase__      (							cls  :				Optional[int]							,  *lowerCAmelCase__  :				int							,  **lowerCAmelCase__  :				int		):





					"""simple docstring"""






					requires_backends(cls							,  ["""onnx"""]		)



			@classmethod
			def UpperCamelCase__      (							cls  :				Tuple							,  *lowerCAmelCase__  :				List[str]							,  **lowerCAmelCase__  :				Optional[Any]		):





					"""simple docstring"""






					requires_backends(cls							,  ["""onnx"""]		)