


"""simple docstring"""



from __future__ import annotations







def     __lowerCAmelCase		(		lowercase    :    list[int]		,				lowercase    :    int					)      ->		list[list[int]]:


    """simple docstring"""





    snake_case       : list[list[int]]    =       []
    snake_case       : list[int]    =       []
    snake_case       : Any    =       0
    snake_case       : Union[str, Any]    =       sum(lowercase					)
    create_state_space_tree(lowercase		,				lowercase		,				lowercase		,				lowercase		,				lowercase		,				lowercase					)
    return result







def     __lowerCAmelCase		(		lowercase    :    list[int]		,				lowercase    :    int		,				lowercase    :    int		,				lowercase    :    list[int]		,				lowercase    :    list[list[int]]		,				lowercase    :    int		,				)      ->		None:


    """simple docstring"""





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


print(*result)









"""simple docstring"""



import os
import sys
import tempfile
import unittest
import unittest.mock as mock
from pathlib import Path

from huggingface_hub import HfFolder, delete_repo
from huggingface_hub.file_download import http_get
from requests.exceptions import HTTPError

from transformers import (
    AlbertTokenizer,
    AutoTokenizer,
    BertTokenizer,
    BertTokenizerFast,
    GPTaTokenizerFast,
    is_tokenizers_available,
)
from transformers.testing_utils import TOKEN, USER, is_staging_test, require_tokenizers
from transformers.tokenization_utils import Trie


sys.path.append(str(Path(__file__).parent.parent / """utils"""))

from test_module.custom_tokenization import CustomTokenizer  # noqa E402


if is_tokenizers_available():
  from test_module.custom_tokenization_fast import CustomTokenizerFast







class _lowerCAmelCase							( unittest.TestCase      ):







   def 					lowerCamelCase						(      self		)      ->						str:

       '''simple docstring'''




       snake_case       : List[str]    =       mock.Mock()
       snake_case       : Any    =       500
       snake_case       : int    =       {}
       snake_case       : int    =       HTTPError
       snake_case       : Dict    =       {}

       # Download this model to make sure it's in the cache.
       snake_case       : Dict    =       BertTokenizer.from_pretrained("hf-internal-testing/tiny-random-bert"		)

       # Under the mock environment we get a 500 error when trying to reach the tokenizer.
       with mock.patch("requests.Session.request"		,      return_value=UpperCamelCase__		) as mock_head:
           snake_case       : str    =       BertTokenizer.from_pretrained("hf-internal-testing/tiny-random-bert"		)
           # This check we did call the fake head request
           mock_head.assert_called()







   @require_tokenizers
   def 					lowerCamelCase						(      self		)      ->						int:

       '''simple docstring'''




       snake_case       : Union[str, Any]    =       mock.Mock()
       snake_case       : int    =       500
       snake_case       : Optional[int]    =       {}
       snake_case       : int    =       HTTPError
       snake_case       : int    =       {}

       # Download this model to make sure it's in the cache.
       snake_case       : Any    =       GPTaTokenizerFast.from_pretrained("gpt2"		)

       # Under the mock environment we get a 500 error when trying to reach the tokenizer.
       with mock.patch("requests.Session.request"		,      return_value=UpperCamelCase__		) as mock_head:
           snake_case       : Tuple    =       GPTaTokenizerFast.from_pretrained("gpt2"		)
           # This check we did call the fake head request
           mock_head.assert_called()







   def 					lowerCamelCase						(      self		)      ->						List[str]:

       '''simple docstring'''




       try:
           snake_case       : Tuple    =       tempfile.mktemp()
           with open(UpperCamelCase__		,      "wb"		) as f:
               http_get("https://huggingface.co/albert-base-v1/resolve/main/spiece.model"		,      UpperCamelCase__		)

           snake_case       : List[str]    =       AlbertTokenizer.from_pretrained(UpperCamelCase__		)
       finally:
           os.remove(UpperCamelCase__		)

       # Supporting this legacy load introduced a weird bug where the tokenizer would load local files if they are in
       # the current folder and have the right name.
       if os.path.isfile("tokenizer.json"		):
           # We skip the test if the user has a `tokenizer.json` in this folder to avoid deleting it.
           return
       try:
           with open("tokenizer.json"		,      "wb"		) as f:
               http_get("https://huggingface.co/hf-internal-testing/tiny-random-bert/blob/main/tokenizer.json"		,      UpperCamelCase__		)
           snake_case       : Dict    =       AutoTokenizer.from_pretrained("hf-internal-testing/tiny-random-gpt2"		)
           # The tiny random BERT has a vocab size of 1024, tiny gpt2 as a vocab size of 1000
           self.assertEqual(tokenizer.vocab_size		,      1000		)
           # Tokenizer should depend on the remote checkpoint, not the local tokenizer.json file.

       finally:
           os.remove("tokenizer.json"		)







   def 					lowerCamelCase						(      self		)      ->						Optional[Any]:

       '''simple docstring'''




       snake_case       : int    =       AlbertTokenizer.from_pretrained("https://huggingface.co/albert-base-v1/resolve/main/spiece.model"		)







@is_staging_test
class _lowerCAmelCase							( unittest.TestCase      ):
   __UpperCAmelCase					:			Dict				    =    ['''[UNK]''', '''[CLS]''', '''[SEP]''', '''[PAD]''', '''[MASK]''', '''bla''', '''blou''']







   @classmethod
   def 					lowerCamelCase						(      cls		)      ->						Optional[int]:

       '''simple docstring'''




       snake_case       : List[str]    =       TOKEN
       HfFolder.save_token(UpperCamelCase__		)







   @classmethod
   def 					lowerCamelCase						(      cls		)      ->						Union[str, Any]:

       '''simple docstring'''




       try:
           delete_repo(token=cls._token		,      repo_id="test-tokenizer"		)
       except HTTPError:
           pass

       try:
           delete_repo(token=cls._token		,      repo_id="valid_org/test-tokenizer-org"		)
       except HTTPError:
           pass

       try:
           delete_repo(token=cls._token		,      repo_id="test-dynamic-tokenizer"		)
       except HTTPError:
           pass







   def 					lowerCamelCase						(      self		)      ->						Dict:

       '''simple docstring'''




       with tempfile.TemporaryDirectory() as tmp_dir:
           snake_case       : Any    =       os.path.join(UpperCamelCase__		,      "vocab.txt"		)
           with open(UpperCamelCase__		,      "w"		,      encoding="utf-8"		) as vocab_writer:
               vocab_writer.write("".join([x + "\n" for x in self.vocab_tokens]		)		)
           snake_case       : List[str]    =       BertTokenizer(UpperCamelCase__		)

       tokenizer.push_to_hub("test-tokenizer"		,      use_auth_token=self._token		)
       snake_case       : Dict    =       BertTokenizer.from_pretrained(F'{USER}/test-tokenizer'		)
       self.assertDictEqual(new_tokenizer.vocab		,      tokenizer.vocab		)

       # Reset repo
       delete_repo(token=self._token		,      repo_id="test-tokenizer"		)

       # Push to hub via save_pretrained
       with tempfile.TemporaryDirectory() as tmp_dir:
           tokenizer.save_pretrained(UpperCamelCase__		,      repo_id="test-tokenizer"		,      push_to_hub=UpperCamelCase__		,      use_auth_token=self._token		)

       snake_case       : Dict    =       BertTokenizer.from_pretrained(F'{USER}/test-tokenizer'		)
       self.assertDictEqual(new_tokenizer.vocab		,      tokenizer.vocab		)







   def 					lowerCamelCase						(      self		)      ->						Any:

       '''simple docstring'''




       with tempfile.TemporaryDirectory() as tmp_dir:
           snake_case       : Dict    =       os.path.join(UpperCamelCase__		,      "vocab.txt"		)
           with open(UpperCamelCase__		,      "w"		,      encoding="utf-8"		) as vocab_writer:
               vocab_writer.write("".join([x + "\n" for x in self.vocab_tokens]		)		)
           snake_case       : Optional[int]    =       BertTokenizer(UpperCamelCase__		)

       tokenizer.push_to_hub("valid_org/test-tokenizer-org"		,      use_auth_token=self._token		)
       snake_case       : Dict    =       BertTokenizer.from_pretrained("valid_org/test-tokenizer-org"		)
       self.assertDictEqual(new_tokenizer.vocab		,      tokenizer.vocab		)

       # Reset repo
       delete_repo(token=self._token		,      repo_id="valid_org/test-tokenizer-org"		)

       # Push to hub via save_pretrained
       with tempfile.TemporaryDirectory() as tmp_dir:
           tokenizer.save_pretrained(
               UpperCamelCase__		,      repo_id="valid_org/test-tokenizer-org"		,      push_to_hub=UpperCamelCase__		,      use_auth_token=self._token		)

       snake_case       : Optional[int]    =       BertTokenizer.from_pretrained("valid_org/test-tokenizer-org"		)
       self.assertDictEqual(new_tokenizer.vocab		,      tokenizer.vocab		)







   @require_tokenizers
   def 					lowerCamelCase						(      self		)      ->						Union[str, Any]:

       '''simple docstring'''




       CustomTokenizer.register_for_auto_class()
       with tempfile.TemporaryDirectory() as tmp_dir:
           snake_case       : Tuple    =       os.path.join(UpperCamelCase__		,      "vocab.txt"		)
           with open(UpperCamelCase__		,      "w"		,      encoding="utf-8"		) as vocab_writer:
               vocab_writer.write("".join([x + "\n" for x in self.vocab_tokens]		)		)
           snake_case       : Any    =       CustomTokenizer(UpperCamelCase__		)

       # No fast custom tokenizer
       tokenizer.push_to_hub("test-dynamic-tokenizer"		,      use_auth_token=self._token		)

       snake_case       : Union[str, Any]    =       AutoTokenizer.from_pretrained(F'{USER}/test-dynamic-tokenizer'		,      trust_remote_code=UpperCamelCase__		)
       # Can't make an isinstance check because the new_model.config is from the CustomTokenizer class of a dynamic module
       self.assertEqual(tokenizer.__class__.__name__		,      "CustomTokenizer"		)

       # Fast and slow custom tokenizer
       CustomTokenizerFast.register_for_auto_class()
       with tempfile.TemporaryDirectory() as tmp_dir:
           snake_case       : int    =       os.path.join(UpperCamelCase__		,      "vocab.txt"		)
           with open(UpperCamelCase__		,      "w"		,      encoding="utf-8"		) as vocab_writer:
               vocab_writer.write("".join([x + "\n" for x in self.vocab_tokens]		)		)

           snake_case       : Optional[Any]    =       BertTokenizerFast.from_pretrained(UpperCamelCase__		)
           bert_tokenizer.save_pretrained(UpperCamelCase__		)
           snake_case       : List[Any]    =       CustomTokenizerFast.from_pretrained(UpperCamelCase__		)

       tokenizer.push_to_hub("test-dynamic-tokenizer"		,      use_auth_token=self._token		)

       snake_case       : Union[str, Any]    =       AutoTokenizer.from_pretrained(F'{USER}/test-dynamic-tokenizer'		,      trust_remote_code=UpperCamelCase__		)
       # Can't make an isinstance check because the new_model.config is from the FakeConfig class of a dynamic module
       self.assertEqual(tokenizer.__class__.__name__		,      "CustomTokenizerFast"		)
       snake_case       : Optional[Any]    =       AutoTokenizer.from_pretrained(
           F'{USER}/test-dynamic-tokenizer'		,      use_fast=UpperCamelCase__		,      trust_remote_code=UpperCamelCase__		)
       # Can't make an isinstance check because the new_model.config is from the FakeConfig class of a dynamic module
       self.assertEqual(tokenizer.__class__.__name__		,      "CustomTokenizer"		)







class _lowerCAmelCase							( unittest.TestCase      ):







   def 					lowerCamelCase						(      self		)      ->						str:

       '''simple docstring'''




       snake_case       : Any    =       Trie()
       trie.add("Hello 友達"		)
       self.assertEqual(trie.data		,      {"H": {"e": {"l": {"l": {"o": {" ": {"友": {"達": {"": 1}}}}}}}}}		)
       trie.add("Hello"		)
       trie.data
       self.assertEqual(trie.data		,      {"H": {"e": {"l": {"l": {"o": {"": 1, " ": {"友": {"達": {"": 1}}}}}}}}}		)







   def 					lowerCamelCase						(      self		)      ->						Any:

       '''simple docstring'''




       snake_case       : Tuple    =       Trie()
       self.assertEqual(trie.split("[CLS] This is a extra_id_100"		)		,      ["[CLS] This is a extra_id_100"]		)
       trie.add("[CLS]"		)
       trie.add("extra_id_1"		)
       trie.add("extra_id_100"		)
       self.assertEqual(trie.split("[CLS] This is a extra_id_100"		)		,      ["[CLS]", " This is a ", "extra_id_100"]		)







   def 					lowerCamelCase						(      self		)      ->						List[str]:

       '''simple docstring'''




       snake_case       : str    =       Trie()
       trie.add("A"		)
       self.assertEqual(trie.split("ABC"		)		,      ["A", "BC"]		)
       self.assertEqual(trie.split("BCA"		)		,      ["BC", "A"]		)







   def 					lowerCamelCase						(      self		)      ->						int:

       '''simple docstring'''




       snake_case       : Union[str, Any]    =       Trie()
       trie.add("TOKEN]"		)
       trie.add("[SPECIAL_TOKEN]"		)
       self.assertEqual(trie.split("This is something [SPECIAL_TOKEN]"		)		,      ["This is something ", "[SPECIAL_TOKEN]"]		)







   def 					lowerCamelCase						(      self		)      ->						Tuple:

       '''simple docstring'''




       snake_case       : Optional[int]    =       Trie()
       trie.add("A"		)
       trie.add("P"		)
       trie.add("[SPECIAL_TOKEN]"		)
       self.assertEqual(trie.split("This is something [SPECIAL_TOKEN]"		)		,      ["This is something ", "[SPECIAL_TOKEN]"]		)







   def 					lowerCamelCase						(      self		)      ->						List[str]:

       '''simple docstring'''




       snake_case       : List[Any]    =       Trie()
       trie.add("AB"		)
       trie.add("B"		)
       trie.add("C"		)
       self.assertEqual(trie.split("ABC"		)		,      ["AB", "C"]		)







   def 					lowerCamelCase						(      self		)      ->						Dict:

       '''simple docstring'''




       snake_case       : str    =       Trie()
       trie.add("ABC"		)
       trie.add("B"		)
       trie.add("CD"		)
       self.assertEqual(trie.split("ABCD"		)		,      ["ABC", "D"]		)







   def 					lowerCamelCase						(      self		)      ->						Optional[Any]:

       '''simple docstring'''




       snake_case       : Optional[int]    =       Trie()
       snake_case       : Union[str, Any]    =       trie.cut_text("ABC"		,      [0, 0, 2, 1, 2, 3]		)
       self.assertEqual(UpperCamelCase__		,      ["AB", "C"]		)





