


'''simple docstring'''

def       __UpperCamelCase	(       UpperCAmelCase		,					UpperCAmelCase		,					UpperCAmelCase					):

 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(a__					)
def       __UpperCamelCase	(       UpperCAmelCase		,					UpperCAmelCase		,					UpperCAmelCase					):

 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]
  lowercase__    :   int						= sum(
      count_of_possible_combinations_with_dp_array(target - item		,					a__					)
      for item in array					)
  lowercase__    :   Tuple						= answer
  return answer

 lowercase__    :   Optional[int]						= [-1] * (target + 1)
 return count_of_possible_combinations_with_dp_array(a__		,					a__					)
def       __UpperCamelCase	(       UpperCAmelCase		,					UpperCAmelCase		,					UpperCAmelCase					):
 lowercase__    :   str						= [0] * (target + 1)
 lowercase__    :   List[Any]						= 1

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

 return dp_array[target]


if __name__ == "__main__":
  import doctest

  doctest.testmod()
  __a:			Tuple	       =       3
  __a:			Tuple	       =       5
  __a:			List[str]	       =       [1, 2, 5]
  print(combination_sum_iv(n, array, target))


'''simple docstring'''

class       UpperCAmelCase  :





       '''simple docstring'''



       def __init__(						self			)  ->  List[str]:
        lowercase__    :   Dict						= {}

       def _lowerCAmelCase(						self			)  ->  None:
        print(self.vertex			)
        for i in self.vertex:
         print(__lowerCAmelCase     ,       ''' -> '''     ,       ''' -> '''.join([str(__lowerCAmelCase			) for j in self.vertex[i]]			)			)

       def _lowerCAmelCase(						self     ,       __lowerCAmelCase     ,       __lowerCAmelCase			)  ->  None:
        # check if vertex is already present,
        if from_vertex in self.vertex:
         self.vertex[from_vertex].append(__lowerCAmelCase			)
        else:
         # else make a new vertex
         lowercase__    :   Union[str, Any]						= [to_vertex]

       def _lowerCAmelCase(						self			)  ->  None:
        # visited array for storing already visited nodes
        lowercase__    :   str						= [False] * len(self.vertex			)

        # call the recursive helper function
        for i in range(len(self.vertex			)			):
         if not visited[i]:
          self.dfs_recursive(__lowerCAmelCase     ,       __lowerCAmelCase			)


       def _lowerCAmelCase(						self     ,       __lowerCAmelCase     ,       __lowerCAmelCase			)  ->  None:
        # mark start vertex as visited
        lowercase__    :   List[str]						= True

        print(__lowerCAmelCase     ,       end=''' '''			)

        # Recur for all the vertices that are adjacent to this node
        for i in self.vertex:
         if not visited[i]:
          self.dfs_recursive(__lowerCAmelCase     ,       __lowerCAmelCase			)


if __name__ == "__main__":
  __a:			Optional[Any]	       =       Graph()
  g.add_edge(0, 1)
  g.add_edge(0, 2)
  g.add_edge(1, 2)
  g.add_edge(2, 0)
  g.add_edge(2, 3)
  g.add_edge(3, 3)

  g.print_graph()
  print("""DFS:""")
  g.dfs()

  # OUTPUT:
  # 0  ->  1 -> 2
  # 1  ->  2
  # 2  ->  0 -> 3
  # 3  ->  3
  # DFS:
  #  0 1 2 3

