

"""simple docstring"""






from __future__ import annotations

def 		lowerCamelCase__		(       _lowerCamelCase			, _lowerCamelCase ):

    '''simple docstring'''



    _lowerCAmelCase							: int	=     get_failure_array(_lowerCamelCase )

    # 2) Step through text searching for pattern
    _lowerCAmelCase,       _lowerCAmelCase							: Optional[int]	=     0, 0  # index into text, pattern
    while i < len(_lowerCamelCase ):
        if pattern[j] == text[i]:
            if j == (len(_lowerCamelCase ) - 1):
                return True
            j += 1

        # if this is a prefix in our pattern
        # just go back far enough to continue
        elif j > 0:
            _lowerCAmelCase							: List[str]	=     failure[j - 1]
            continue
        i += 1
    return False

def 		lowerCamelCase__		(       _lowerCamelCase ):

    '''simple docstring'''



    _lowerCAmelCase							: List[str]	=     [0]
    _lowerCAmelCase							: List[Any]	=     0
    _lowerCAmelCase							: Union[str, Any]	=     1
    while j < len(_lowerCamelCase ):
        if pattern[i] == pattern[j]:
            i += 1
        elif i > 0:
            _lowerCAmelCase							: List[str]	=     failure[i - 1]
            continue
        j += 1
        failure.append(_lowerCamelCase )
    return failure


if __name__ == "__main__":
 # Test 1)
 _lowerCAmelCase       						=		"""abc1abc12"""
 _lowerCAmelCase       						=		"""alskfjaldsabc1abc1abc12k23adsfabcabc"""
 _lowerCAmelCase       						=		"""alskfjaldsk23adsfabcabc"""
 assert kmp(pattern, texta) and not kmp(pattern, texta)

 # Test 2)
 _lowerCAmelCase       						=		"""ABABX"""
 _lowerCAmelCase       						=		"""ABABZABABYABABX"""
 assert kmp(pattern, text)

 # Test 3)
 _lowerCAmelCase       						=		"""AAAB"""
 _lowerCAmelCase       						=		"""ABAAAAAB"""
 assert kmp(pattern, text)

 # Test 4)
 _lowerCAmelCase       						=		"""abcdabcy"""
 _lowerCAmelCase       						=		"""abcxabcdabxabcdabcdabcy"""
 assert kmp(pattern, text)

 # Test 5)
 _lowerCAmelCase       						=		"""aabaabaaa"""
 assert get_failure_array(pattern) == [0, 1, 0, 1, 2, 3, 4, 5, 2]







from __future__ import annotations


def 				__A(lowerCAmelCase    ,	lowerCAmelCase			)		->					list[list[int]]:

		"""simple docstring"""






		_UpperCamelCase         =						[]
		_UpperCamelCase         =						[]
		_UpperCamelCase         =						0
		_UpperCamelCase         =						sum(lowerCAmelCase			)
		create_state_space_tree(lowerCAmelCase    ,	lowerCAmelCase    ,	lowerCAmelCase    ,	lowerCAmelCase    ,	lowerCAmelCase    ,	lowerCAmelCase			)
		return result


def 				__A(lowerCAmelCase    ,	lowerCAmelCase    ,	lowerCAmelCase    ,	lowerCAmelCase    ,	lowerCAmelCase    ,	lowerCAmelCase    ,	)		->					None:

		"""simple docstring"""






		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__						=				[3, 34, 4, 12, 5, 2]
lowerCamelCase__						=				9
lowerCamelCase__						=				generate_sum_of_subsets_soln(nums, max_sum)







print(*result)



