





from __future__ import annotations

from collections.abc import Iterator
class 			UpperCamelCase_		:




					def __init__(		self				,						lowerCAmelCase_  )		->							Any:
												_snake_case									=				value
												_snake_case									=				None
												_snake_case									=				None





class 			UpperCamelCase_		:




					def __init__(		self				,						lowerCAmelCase_  )		->							str:
												_snake_case									=				tree




					def 	lowerCAmelCase			(		self				,						lowerCAmelCase_  )		->							List[Any]:
												if node is None:
																			return 0
												return node.value + (
												    self.depth_first_search(node.left  ) + self.depth_first_search(node.right  )
												)






					def __iter__(		self  )		->							int:
												yield self.depth_first_search(self.tree  )


if __name__ == "__main__":
					import doctest

					doctest.testmod()










def 						lowerCamelCase__     (     UpperCamelCase__			:       list[int]       ,    UpperCamelCase__			:       int						)			-> bool:



					'''simple docstring'''




					_snake_case									=				len(UpperCamelCase__						)
					_snake_case									=				[[False] * (required_sum + 1) for _ in range(arr_len + 1						)]

					# for each arr value, a sum of zero(0) can be formed by not taking any element
					# hence True/1
					for i in range(arr_len + 1						):
										_snake_case									=				True

					# sum is not zero and set is empty then false
					for i in range(1       ,    required_sum + 1						):
										_snake_case									=				False

					for i in range(1       ,    arr_len + 1						):
										for j in range(1       ,    required_sum + 1						):
															if arr[i - 1] > j:
																				_snake_case									=				subset[i - 1][j]
															if arr[i - 1] <= j:
																				_snake_case									=				subset[i - 1][j] or subset[i - 1][j - arr[i - 1]]

					return subset[arr_len][required_sum]


if __name__ == "__main__":
					import doctest

					doctest.testmod()



