


def 			_a      (    __UpperCamelCase	,	__UpperCamelCase	,	__UpperCamelCase	,	__UpperCamelCase	,	__UpperCamelCase			):
     if target == 0:
          answer.append(path.copy()			)
     else:
          for index in range(__UpperCamelCase	,	len(__UpperCamelCase			)			):
               if target >= candidates[index]:
                    path.append(candidates[index]			)
                    backtrack(__UpperCamelCase	,	__UpperCamelCase	,	__UpperCamelCase	,	target - candidates[index]	,	__UpperCamelCase			)
                    path.pop(len(__UpperCamelCase			) - 1			)



def 			_a      (    __UpperCamelCase	,	__UpperCamelCase			):
     a_     :  List[Any]				      =     []  # type: list[int]
     a_     :  Optional[int]				      =     []  # type: list[int]
     backtrack(__UpperCamelCase	,	__UpperCamelCase	,	__UpperCamelCase	,	__UpperCamelCase	,	0			)
     return answer



def 			_a      (    ):
     print(combination_sum([-8, 2.3, 0]	,	1			)			)


if __name__ == "__main__":
       import doctest

       doctest.testmod()
       main()











"""simple docstring"""



from __future__ import annotations

import copy
import os
import tempfile
from importlib import import_module
from math import isnan

from transformers import is_tf_available
from transformers.models.auto import get_values
from transformers.testing_utils import _tf_gpu_memory_limit, require_tf, slow

from ..test_modeling_tf_common import ids_tensor


if is_tf_available():
    import numpy as np
    import tensorflow as tf

    from transformers import (
        TF_MODEL_FOR_CAUSAL_LM_MAPPING,
        TF_MODEL_FOR_IMAGE_CLASSIFICATION_MAPPING,
        TF_MODEL_FOR_MASKED_LM_MAPPING,
        TF_MODEL_FOR_MULTIPLE_CHOICE_MAPPING,
        TF_MODEL_FOR_NEXT_SENTENCE_PREDICTION_MAPPING,
        TF_MODEL_FOR_PRETRAINING_MAPPING,
        TF_MODEL_FOR_QUESTION_ANSWERING_MAPPING,
        TF_MODEL_FOR_SEQ_TO_SEQ_CAUSAL_LM_MAPPING,
        TF_MODEL_FOR_SEQUENCE_CLASSIFICATION_MAPPING,
        TF_MODEL_FOR_TOKEN_CLASSIFICATION_MAPPING,
        TFSharedEmbeddings,
    )

    if _tf_gpu_memory_limit is not None:
        _UpperCamelCase						:    int		=						tf.config.list_physical_devices('GPU')
        for gpu in gpus:
            # Restrict TensorFlow to only allocate x GB of memory on the GPUs
            try:
                tf.config.set_logical_device_configuration(
                    gpu, [tf.config.LogicalDeviceConfiguration(memory_limit=_tf_gpu_memory_limit)]
                )
                _UpperCamelCase						:    Any		=						tf.config.list_logical_devices('GPU')
                print('Logical GPUs', logical_gpus)
            except RuntimeError as e:
                # Virtual devices must be set before GPUs have been initialized
                print(e)

@require_tf
class 			a	:
    UpperCAmelCase_					:	Union[str, Any]      	=None
    UpperCAmelCase_					:	Any      	=()
    UpperCAmelCase_					:	Optional[int]      	=()
    UpperCAmelCase_					:	Any      	=True
    UpperCAmelCase_					:	int      	=True
    UpperCAmelCase_					:	Dict      	=True
    UpperCAmelCase_					:	Any      	=False







    def      UpperCamelCase_ (     self				,						_lowerCamelCase				,						_lowerCamelCase				,						_lowerCamelCase=False			):
      lowercase				       =			copy.deepcopy(_lowerCamelCase			)

      if model_class in get_values(_lowerCamelCase			):
        lowercase				       =			{
            k: tf.tile(tf.expand_dims(_lowerCamelCase				,						1			)				,						(1, self.model_tester.num_choices) + (1,) * (v.ndim - 1)			)
            if isinstance(_lowerCamelCase				,						tf.Tensor			) and v.ndim > 0
            else v
            for k, v in inputs_dict.items()
        }

      if return_labels:
        if model_class in get_values(_lowerCamelCase			):
          lowercase				       =			tf.ones(self.model_tester.batch_size				,						dtype=tf.intaa			)
        elif model_class in get_values(_lowerCamelCase			):
          lowercase				       =			tf.zeros(self.model_tester.batch_size				,						dtype=tf.intaa			)
          lowercase				       =			tf.zeros(self.model_tester.batch_size				,						dtype=tf.intaa			)
        elif model_class in [
            *get_values(_lowerCamelCase			),
            *get_values(_lowerCamelCase			),
        ]:
          lowercase				       =			tf.zeros(self.model_tester.batch_size				,						dtype=tf.intaa			)
        elif model_class in get_values(_lowerCamelCase			):
          lowercase				       =			tf.zeros(self.model_tester.batch_size				,						dtype=tf.intaa			)
        elif model_class in [
            *get_values(_lowerCamelCase			),
            *get_values(_lowerCamelCase			),
            *get_values(_lowerCamelCase			),
            *get_values(_lowerCamelCase			),
            *get_values(_lowerCamelCase			),
        ]:
          lowercase				       =			tf.zeros(
              (self.model_tester.batch_size, self.model_tester.seq_length)				,						dtype=tf.intaa			)
      return inputs_dict







    @slow
    def      UpperCamelCase_ (     self			):
      lowercase       ,	lowercase				       =			self.model_tester.prepare_config_and_inputs_for_common()
      for model_class in self.all_model_classes[:2]:
        lowercase				       =			self._prepare_for_class(_lowerCamelCase				,						_lowerCamelCase			)
        lowercase				       =			model_class(_lowerCamelCase			)

        @tf.function
        def run_in_graph_mode():
          return model(_lowerCamelCase			)

        lowercase				       =			run_in_graph_mode()
        self.assertIsNotNone(_lowerCamelCase			)







    @slow
    def      UpperCamelCase_ (     self			):
      lowercase       ,	lowercase				       =			self.model_tester.prepare_config_and_inputs_for_common()
      for model_class in self.all_model_classes[:2]:
        lowercase				       =			self._prepare_for_class(_lowerCamelCase				,						_lowerCamelCase			)
        lowercase				       =			model_class(_lowerCamelCase			)

        @tf.function(experimental_compile=_lowerCamelCase			)
        def run_in_graph_mode():
          return model(_lowerCamelCase			)

        lowercase				       =			run_in_graph_mode()
        self.assertIsNotNone(_lowerCamelCase			)







    @slow
    def      UpperCamelCase_ (     self			):
      # This is a copy of the test_keras_fit method, but we use XLA compilation instead of eager
      lowercase       ,	lowercase				       =			self.model_tester.prepare_config_and_inputs_for_common()
      for model_class in self.all_model_classes[:2]:
        lowercase				       =			model_class(_lowerCamelCase			)
        if getattr(_lowerCamelCase				,						'hf_compute_loss'				,						_lowerCamelCase			):
          # Test that model correctly compute the loss with kwargs
          lowercase				       =			self._prepare_for_class(inputs_dict.copy()				,						_lowerCamelCase				,						return_labels=_lowerCamelCase			)
          # Is there a better way to remove these decoder inputs?
          lowercase				       =			{
              key: val
              for key, val in prepared_for_class.items()
              if key not in ('head_mask', 'decoder_head_mask', 'cross_attn_head_mask', 'decoder_input_ids')
          }

          lowercase				       =			{
              'labels',
              'label',
              'label_ids',
              'start_positions',
              'start_position',
              'end_positions',
              'end_position',
              'next_sentence_label',
          }
          lowercase				       =			possible_label_cols.intersection(set(_lowerCamelCase			)			)
          self.assertGreater(len(_lowerCamelCase			)				,						0				,						msg='No matching label names found!'			)
          lowercase				       =			{key: val for key, val in prepared_for_class.items() if key in label_names}
          lowercase				       =			{key: val for key, val in prepared_for_class.items() if key not in label_names}
          self.assertGreater(len(_lowerCamelCase			)				,						0			)

          # Make sure it works with XLA!
          model.compile(optimizer=tf.keras.optimizers.SGD(0.0			)				,						jit_compile=_lowerCamelCase			)
          # Make sure the model fits without crashing regardless of where we pass the labels
          lowercase				       =			model.fit(
              _lowerCamelCase				,						validation_data=_lowerCamelCase				,						steps_per_epoch=1				,						validation_steps=1				,						shuffle=_lowerCamelCase				,						verbose=0				,						)
          lowercase				       =			history.history['loss'][0]
          self.assertTrue(not isnan(_lowerCamelCase			)			)
          lowercase				       =			history.history['val_loss'][0]
          self.assertTrue(not isnan(_lowerCamelCase			)			)

          # Now test it with separate labels, to make sure that path works in XLA too.
          lowercase				       =			model_class(_lowerCamelCase			)
          model.compile(optimizer=tf.keras.optimizers.SGD(0.0			)				,						jit_compile=_lowerCamelCase			)
          lowercase				       =			model.fit(
              _lowerCamelCase				,						_lowerCamelCase				,						validation_data=(inputs_minus_labels, labels)				,						steps_per_epoch=1				,						validation_steps=1				,						shuffle=_lowerCamelCase				,						verbose=0				,						)

          lowercase				       =			history.history['loss'][0]
          self.assertTrue(not isnan(_lowerCamelCase			)			)
          lowercase				       =			history.history['val_loss'][0]
          self.assertTrue(not isnan(_lowerCamelCase			)			)







    @slow
    def      UpperCamelCase_ (     self			):
      lowercase       ,	lowercase				       =			self.model_tester.prepare_config_and_inputs_for_common()
      lowercase				       =			True
      lowercase				       =			True

      if hasattr(_lowerCamelCase				,						'use_cache'			):
        lowercase				       =			True

      lowercase				       =			getattr(self.model_tester				,						'encoder_seq_length'				,						self.model_tester.seq_length			)
      lowercase				       =			getattr(self.model_tester				,						'key_length'				,						_lowerCamelCase			)

      for model_class in self.all_model_classes[:2]:
        lowercase				       =			self._prepare_for_class(_lowerCamelCase				,						_lowerCamelCase			)
        lowercase				       =			model_class(_lowerCamelCase			)
        model.build()
        lowercase				       =			len(model(_lowerCamelCase			)			)

        for key in list(class_inputs_dict.keys()			):
          # Remove keys not in the serving signature, as the SavedModel will not be compiled to deal with them
          if key not in model.input_signature:
            del class_inputs_dict[key]
          # Check it's a tensor, in case the inputs dict has some bools in it too
          elif isinstance(class_inputs_dict[key]				,						tf.Tensor			) and class_inputs_dict[key].dtype.is_integer:
            lowercase				       =			tf.cast(class_inputs_dict[key]				,						tf.intaa			)

        if set(class_inputs_dict.keys()			) != set(model.input_signature.keys()			):
          continue  # Some models have inputs that the preparation functions don't create, we skip those

        with tempfile.TemporaryDirectory() as tmpdirname:
          model.save_pretrained(_lowerCamelCase				,						saved_model=_lowerCamelCase			)
          lowercase				       =			os.path.join(_lowerCamelCase				,						'saved_model'				,						'1'			)
          lowercase				       =			tf.keras.models.load_model(_lowerCamelCase			)
          lowercase				       =			model(_lowerCamelCase			)

          if self.is_encoder_decoder:
            lowercase				       =			outputs['encoder_hidden_states']
            lowercase				       =			outputs['encoder_attentions']
          else:
            lowercase				       =			outputs['hidden_states']
            lowercase				       =			outputs['attentions']

          self.assertEqual(len(_lowerCamelCase			)				,						_lowerCamelCase			)

          lowercase				       =			getattr(
              self.model_tester				,						'expected_num_hidden_layers'				,						self.model_tester.num_hidden_layers + 1			)

          self.assertEqual(len(_lowerCamelCase			)				,						_lowerCamelCase			)
          self.assertListEqual(
              list(output_hidden_states[0].shape[-2:]			)				,						[self.model_tester.seq_length, self.model_tester.hidden_size]				,						)

          self.assertEqual(len(_lowerCamelCase			)				,						self.model_tester.num_hidden_layers			)
          self.assertListEqual(
              list(output_attentions[0].shape[-3:]			)				,						[self.model_tester.num_attention_heads, encoder_seq_length, encoder_key_length]				,						)







    @slow
    def      UpperCamelCase_ (     self			):
      tf.keras.mixed_precision.set_global_policy('mixed_float16'			)

      # try/finally block to ensure subsequent tests run in float32
      try:
        lowercase       ,	lowercase				       =			self.model_tester.prepare_config_and_inputs_for_common()
        for model_class in self.all_model_classes[:2]:
          lowercase				       =			self._prepare_for_class(_lowerCamelCase				,						_lowerCamelCase			)
          lowercase				       =			model_class(_lowerCamelCase			)
          lowercase				       =			model(_lowerCamelCase			)

          self.assertIsNotNone(_lowerCamelCase			)
      finally:
        tf.keras.mixed_precision.set_global_policy('float32'			)







    @slow
    def      UpperCamelCase_ (     self			):
      lowercase       ,	lowercase				       =			self.model_tester.prepare_config_and_inputs_for_common()
      # head_mask and decoder_head_mask has different shapes than other input args
      if "head_mask" in inputs_dict:
        del inputs_dict["head_mask"]
      if "decoder_head_mask" in inputs_dict:
        del inputs_dict["decoder_head_mask"]
      if "cross_attn_head_mask" in inputs_dict:
        del inputs_dict["cross_attn_head_mask"]
      lowercase				       =			{
          module_member
          for model_class in self.all_model_classes
          for module in (import_module(model_class.__module__			),)
          for module_member_name in dir(_lowerCamelCase			)
          if module_member_name.endswith('MainLayer'			)
          for module_member in (getattr(_lowerCamelCase				,						_lowerCamelCase			),)
          if isinstance(_lowerCamelCase				,						_lowerCamelCase			)
          and tf.keras.layers.Layer in module_member.__bases__
          and getattr(_lowerCamelCase				,						'_keras_serializable'				,						_lowerCamelCase			)
      }

      for main_layer_class in tf_main_layer_classes:
        # T5MainLayer needs an embed_tokens parameter when called without the inputs_embeds parameter
        if "T5" in main_layer_class.__name__:
          # Take the same values than in TFT5ModelTester for this shared layer
          lowercase				       =			TFSharedEmbeddings(self.model_tester.vocab_size				,						self.model_tester.hidden_size				,						name='shared'			)
          lowercase				       =			False
          lowercase				       =			main_layer_class(_lowerCamelCase				,						embed_tokens=_lowerCamelCase			)
        else:
          lowercase				       =			main_layer_class(_lowerCamelCase			)

        lowercase				       =			{
            name: tf.keras.Input(tensor.shape[1:]				,						dtype=tensor.dtype			) for name, tensor in inputs_dict.items()
        }

        if hasattr(self.model_tester				,						'num_labels'			):
          lowercase				       =			self.model_tester.num_labels
        else:
          lowercase				       =			2

        lowercase				       =			tf.data.Dataset.from_tensor_slices(
            (inputs_dict, np.ones((self.model_tester.batch_size, self.model_tester.seq_length, num_labels, 1)			))			).batch(1			)

        lowercase				       =			main_layer(_lowerCamelCase			)[0]
        lowercase				       =			tf.keras.layers.Dense(_lowerCamelCase				,						activation='softmax'				,						name='outputs'			)(_lowerCamelCase			)
        lowercase				       =			tf.keras.models.Model(inputs=_lowerCamelCase				,						outputs=[outputs]			)

        model.compile(loss='binary_crossentropy'				,						optimizer='adam'				,						metrics=['binary_accuracy']			)
        model.fit(_lowerCamelCase				,						epochs=1			)

        with tempfile.TemporaryDirectory() as tmpdirname:
          lowercase				       =			os.path.join(_lowerCamelCase				,						'keras_model.h5'			)
          model.save(_lowerCamelCase			)
          if "T5" in main_layer_class.__name__:
            lowercase				       =			tf.keras.models.load_model(
                _lowerCamelCase				,						custom_objects={
                    main_layer_class.__name__: main_layer_class,
                    'TFSharedEmbeddings': TFSharedEmbeddings,
                }				,						)
          else:
            lowercase				       =			tf.keras.models.load_model(
                _lowerCamelCase				,						custom_objects={main_layer_class.__name__: main_layer_class}			)
          assert isinstance(_lowerCamelCase				,						tf.keras.Model			)
          model(_lowerCamelCase			)







    @slow
    def      UpperCamelCase_ (     self			):
      lowercase       ,	lowercase				       =			self.model_tester.prepare_config_and_inputs_for_common()

      for model_class in self.all_model_classes[:2]:
        lowercase				       =			model_class(_lowerCamelCase			)

        lowercase				       =			copy.deepcopy(_lowerCamelCase			)

        if not self.is_encoder_decoder:
          lowercase				       =			inputs['input_ids']
          del inputs["input_ids"]
        else:
          lowercase				       =			inputs['input_ids']
          lowercase				       =			inputs.get('decoder_input_ids'				,						_lowerCamelCase			)
          del inputs["input_ids"]
          inputs.pop('decoder_input_ids'				,						_lowerCamelCase			)

        if not self.is_encoder_decoder:
          lowercase				       =			model.get_input_embeddings()(_lowerCamelCase			)
        else:
          lowercase				       =			model.get_input_embeddings()(_lowerCamelCase			)
          lowercase				       =			model.get_input_embeddings()(_lowerCamelCase			)

        lowercase				       =			self._prepare_for_class(_lowerCamelCase				,						_lowerCamelCase			)

        @tf.function
        def run_in_graph_mode():
          return model(_lowerCamelCase			)

        lowercase				       =			run_in_graph_mode()
        self.assertIsNotNone(_lowerCamelCase			)







    def      UpperCamelCase_ (     self				,						_lowerCamelCase				,						_lowerCamelCase			):
      # special tokens cannot be bad tokens
      lowercase				       =			[]
      if model.config.bos_token_id is not None:
        special_tokens.append(model.config.bos_token_id			)
      if model.config.pad_token_id is not None:
        special_tokens.append(model.config.pad_token_id			)
      if model.config.eos_token_id is not None:
        special_tokens.append(model.config.eos_token_id			)

      # create random bad tokens that are not special tokens
      lowercase				       =			[]
      while len(_lowerCamelCase			) < num_bad_tokens:
        lowercase				       =			tf.squeeze(ids_tensor((1, 1)				,						self.model_tester.vocab_size			)				,						0			).numpy()[0]
        if token not in special_tokens:
          bad_tokens.append(_lowerCamelCase			)
      return bad_tokens







    def      UpperCamelCase_ (     self				,						_lowerCamelCase			):
      for token_id in output_ids[0].numpy().tolist():
        self.assertGreaterEqual(_lowerCamelCase				,						0			)
        self.assertLess(_lowerCamelCase				,						self.model_tester.vocab_size			)







    def      UpperCamelCase_ (     self				,						_lowerCamelCase				,						_lowerCamelCase			):
      # for all bad word tokens
      for bad_word_ids in bad_words_ids:
        # for all slices in batch
        for generated_ids_slice in generated_ids:
          # for all word idx
          for i in range(len(_lowerCamelCase			)				,						len(_lowerCamelCase			)			):
            # if tokens match
            if generated_ids_slice[i - len(_lowerCamelCase			) : i] == bad_word_ids:
              return True
      return False


