





from __future__ import annotations

from typing import Generic, TypeVar

_lowerCAmelCase				:   Optional[int]						       =						TypeVar('''T''')


class        __magic_name__	(				Generic[T]				):





     """simple docstring"""



     def __init__(				self							:int      ,   snake_case							:T	):





        '''simple docstring'''




        A_       :					int        =      data
        A_       :					List[str]        =      self
        A_       :					str        =      0




class        __magic_name__	(				Generic[T]				):





     """simple docstring"""



     def __init__(				self							:Optional[int]	):





        '''simple docstring'''




        A_       :					dict[T, DisjointSetTreeNode[T]]        =      {}



     def     SCREAMING_SNAKE_CASE		(				self							:Optional[int]      ,   snake_case							:T	):





        '''simple docstring'''




        A_       :					Union[str, Any]        =      DisjointSetTreeNode(snake_case	)



     def     SCREAMING_SNAKE_CASE		(				self							:Union[str, Any]      ,   snake_case							:T	):





        '''simple docstring'''




        A_       :					Any        =      self.map[data]
        if elem_ref != elem_ref.parent:
           A_       :					Dict        =      self.find_set(elem_ref.parent.data	)
        return elem_ref.parent



     def     SCREAMING_SNAKE_CASE		(				self							:List[Any]      ,   snake_case							:DisjointSetTreeNode[T]      ,   snake_case							:DisjointSetTreeNode[T]	):





        '''simple docstring'''




        if nodea.rank > nodea.rank:
           A_       :					Tuple        =      nodea
        else:
           A_       :					List[str]        =      nodea
           if nodea.rank == nodea.rank:
              nodea.rank += 1





     def     SCREAMING_SNAKE_CASE		(				self							:List[str]      ,   snake_case							:T      ,   snake_case							:T	):





        '''simple docstring'''




        self.link(self.find_set(snake_case	)      ,   self.find_set(snake_case	)	)




class        __magic_name__	(				Generic[T]				):





     """simple docstring"""



     def __init__(				self							:Union[str, Any]	):





        '''simple docstring'''




        A_       :					dict[T, dict[T, int]]        =      {}



     def     SCREAMING_SNAKE_CASE		(				self							:Tuple      ,   snake_case							:T	):





        '''simple docstring'''




        if node not in self.connections:
           A_       :					int        =      {}



     def     SCREAMING_SNAKE_CASE		(				self							:List[Any]      ,   snake_case							:T      ,   snake_case							:T      ,   snake_case							:int	):





        '''simple docstring'''




        self.add_node(snake_case	)
        self.add_node(snake_case	)
        A_       :					Optional[Any]        =      weight
        A_       :					str        =      weight





     def     SCREAMING_SNAKE_CASE		(				self							:Tuple	):





        '''simple docstring'''




        A_       :					List[str]        =      []
        A_       :					Any        =      set()
        for start in self.connections:
           for end in self.connections[start]:
              if (start, end) not in seen:
                 seen.add((end, start)	)
                 edges.append((start, end, self.connections[start][end])	)
        edges.sort(key=lambda snake_case	: x[2]	)

        # creating the disjoint set
        A_       :					str        =      DisjointSetTree[T]()
        for node in self.connections:
           disjoint_set.make_set(snake_case	)

        # MST generation
        A_       :					Tuple        =      0
        A_       :					Tuple        =      0
        A_       :					Any        =      GraphUndirectedWeighted[T]()
        while num_edges < len(self.connections	) - 1:
           A_   ,    A_   ,    A_       :					Union[str, Any]        =      edges[index]
           index += 1
           A_       :					Any        =      disjoint_set.find_set(snake_case	)
           A_       :					int        =      disjoint_set.find_set(snake_case	)
           if parent_u != parent_v:
              num_edges += 1
              graph.add_edge(snake_case      ,   snake_case      ,   snake_case	)
              disjoint_set.union(snake_case      ,   snake_case	)
        return graph







from __future__ import annotations

def   __snake_case    (       _lowerCAmelCase			:			list[int]					,					_lowerCAmelCase			:			int						)			->    list[list[int]]:
   A_       :					list[list[int]]        =      []
   A_       :					list[int]        =      []
   A_       :					Dict        =      0
   A_       :					str        =      sum(_lowerCAmelCase						)
   create_state_space_tree(_lowerCAmelCase					,					_lowerCAmelCase					,					_lowerCAmelCase					,					_lowerCAmelCase					,					_lowerCAmelCase					,					_lowerCAmelCase						)
   return result

def   __snake_case    (       _lowerCAmelCase			:			list[int]					,					_lowerCAmelCase			:			int					,					_lowerCAmelCase			:			int					,					_lowerCAmelCase			:			list[int]					,					_lowerCAmelCase			:			list[list[int]]					,					_lowerCAmelCase			:			int					,					)			->    None:
   if sum(_lowerCAmelCase						) > max_sum or (remaining_nums_sum + sum(_lowerCAmelCase						)) < max_sum:
      return
   if sum(_lowerCAmelCase						) == max_sum:
      result.append(_lowerCAmelCase						)
      return
   for index in range(_lowerCAmelCase					,					len(_lowerCAmelCase						)						):
      create_state_space_tree(
          _lowerCAmelCase					,					_lowerCAmelCase					,					index + 1					,					[*path, nums[index]]					,					_lowerCAmelCase					,					remaining_nums_sum - nums[index]					,					)
_lowerCAmelCase				:   List[Any]						       =						[3, 34, 4, 12, 5, 2]
_lowerCAmelCase				:   Dict						       =						9
_lowerCAmelCase				:   Dict						       =						generate_sum_of_subsets_soln(nums, max_sum)





print(*result)
