Étant donné un tableau d'entiers aqui contient n entiers et un seul entier x; supprimer le moins d'éléments apour que la somme soit aégale à x. Si aucune combinaison de ane peut se former x, renvoyez une valeur fausse.

Comme indiqué dans un commentaire, il s'agit de l'ensemble maximal avec une somme de x , excusez mon cerveau mathématique inférieur. J'ai oublié beaucoup de termes depuis le collège.

Exemples (Truthy):

f([1,2,3,4,5,6,7,8,9,10], 10) = [1,2,3,4]

f([2,2,2,2,2,2,2,2,2], 10) = [2,2,2,2,2]

f([2,2,2,2,-2,-2,-2,-4,-2], -8) = [2,2,-2,-2,-2,-4,-2]

f([-2,-4,-2], -6) = [-4,-2] OR [-2,-4]

f([2,2,2,4,2,-2,-2,-2,-4,-2], 0) = [2,2,2,4,2,-2,-2,-2,-4,-2] (Inchangé)

f([], 0) = [] (Cas à somme nulle inchangé)

Exemples (Falsy, toute valeur non matricielle cohérente):

Impossible de faire l'affaire: f([-2,4,6,-8], 3) = falsy (E.G. -1)

Cas à somme nulle: f([], non-zero number) = falsy (E.G. -1)

• Remarque: toute valeur comme [-1]ne peut pas être valide pour la falsification, car il s'agit d'une sortie véridique potentielle.

Règles:

• L'entrée peut être prise sous forme de tableau ou sous forme de liste d'arguments, le dernier ou le premier étant x.
• La sortie peut être n'importe quelle liste délimitée d'entiers. EG 1\n2\n3\nou [1,2,3].
• Toute valeur peut être utilisée comme indicateur de falsification, autre qu'un tableau d'entiers.
• Votre code doit maximiser la taille du tableau final, l'ordre n'a pas d'importance.
  • EG Pour les f([3,2,3],5)deux [2,3]et [3,2]sont également valables.
  • Par exemple, f([1,1,2],2)vous ne pouvez revenir [1,1]que [2]plus court.
• La somme de aet la valeur de xseront inférieures 2^32-1et supérieures à -2^32-1.
• Il s'agit du code-golf , le plus petit nombre de victoires d'octets.
• S'il existe plusieurs sous-réseaux de même taille qui sont valides, il n'est pas acceptable de les afficher tous. Vous devez en choisir un seul et le sortir.

Faites-moi savoir si cela a été publié, je ne l'ai pas trouvé.

Messages que j'ai trouvés comme ceci : liés mais fermés , ...

Brachylog , 8 octets

h⊇.+~t?∧

Essayez-le en ligne!

Réponse Brachylog mensuelle. Retourne false.si ce n'est pas possible.

Explication

h⊇.           The output is a subset of the head of the input
  .+~t?       The sum of the elements of the output must equal the tail of the input
       ∧      (Avoid implicit unification between the output and the input)

Python 2 , 108 104 octets

lambda a,n:[x for l in range(len(a)+1)for x in combinations(a,l)if sum(x)==n][-1]
from itertools import*

Essayez-le en ligne!

_{-4 octets, merci à Jonathan Allan}

Python 2 , 108 106 octets

def f(a,n):
 q=[a]
 while q:
  x=q.pop(0);q+=[x[:i]+x[i+1:]for i in range(len(x))]
  if sum(x)==n:return x

Essayez-le en ligne!

_{-2 octets, merci à Janathan Frech}

05AB1E , 9 octets

æʒOQ}0ªéθ

Essayez-le en ligne!

Japt -h , 11 octets

à f_x ¥VÃñl

Essayez-le en ligne!

Pyth , 8 octets

• 8 octets ( essayez-le! ) - Produit une seule solution possible. Pour les entrées insolubles, il n'imprime rien dans STDOUT, qui est une chaîne vide, qui est techniquement parlant falsey en Pyth, mais écrit dans STDERR. Merci à FryAmTheEggman d' avoir suggéré cela (en ignorant STDERR et en se concentrant uniquement sur la sortie STDOUT), économisant ainsi 1 octet.

  efqz`sTy    
  

• 9 octets ( Essayez! ) - Produit une seule solution possible, enveloppée dans une liste singleton comme autorisé par défaut (par exemple ([1...10], 10) -> [[1,2,3,4]]; ([], 0) -> [[]]). Pour les entrées insolubles, il revient [], ce qui est falsey en Pyth.

  >1fqz`sTy
  

• 10 octets ( essayez-le! ) - Pour une sortie plus claire, sans utiliser la règle de la liste singleton et en utilisant 0plutôt que []comme valeur falsifiée.

  e+0fqz`sTy
  

Explication

Tout d'abord, le code calcule le jeu de puissance de la liste d'entrée (toutes ses sous-collections ordonnées possibles). Ensuite, il ne conserve que les collections dont la somme est égale au nombre d'entrée. Il convient de noter que les collections sont générées du plus court au plus long, nous nous concentrons donc sur la dernière. Pour l'obtenir:

• Le 8 octets utilise simplement la fin intégrée, ce qui génère une erreur, mais STDERR peut être ignoré selon nos règles de site, la sortie vers STDOUT étant une chaîne vide, ce qui est faux.
• Le 9 octets prend le dernier élément, mais en utilisant le code Python équivalent lst[-1:]à la place de lst[-1]pour éviter que des erreurs ne soient levées pour des entrées insolubles.
• Le 10 octets ajoute un 0 à la liste des sous-collections filtrées, puis prend la fin de cette collection (dernier élément). Si les entrées ne sont pas résolubles, alors 0 est naturellement utilisé à la place.

Gelée , 7 octets

ŒPS⁼¥ƇṪ

Essayez-le en ligne!

Sortie clarifiée sur TIO.

Perl 6 , 38 37 octets

{*.combinations.grep(*.sum==$_).tail}

Essayez-le en ligne!

Fonction curry.

Brachylog , 4 octets

⟨⊇+⟩

Essayez-le en ligne!

À peu près équivalent à Fatalize h⊇.+~t?∧, sauf beaucoup plus court, grâce à la fonction de composition de prédicat qui, selon l'historique de modification de la référence, était un travail en cours jusqu'au 8 janvier, postdatant la réponse de plus de deux mois. ⟨⊇+⟩est un sandwich ,{[I,J]∧I⊇.+J∧} , où les accolades sont dans ce cas hors de propos car le sandwich est de toute façon sur sa propre ligne.

                The input
[I,J]           is a list of two elements I and J.
        .       The output,
         +J     which sums to J
           ∧    (which we don't unify with the output),
      I⊇        is a sublist of I
     ∧          (which we don't unify with [I,J]).

Une transformation beaucoup moins spectaculaire de la réponse de Fatalize, qui utilise les mêmes prédicats avec les mêmes variables mais sort un octet plus court d'être organisé différemment:

Brachylog , 7 octets

h⊇.&t~+

Essayez-le en ligne!

           The input
h          's first element
 ⊇         is a superlist of
  .        the output,
   &       and the input
    t      's last item
     ~+    is the sum of the elements of
           the output.

(De plus, si quelqu'un veut voir quelque chose d'étrange, changez l'un des traits de soulignement des cas de test en traits d'union.)

Pyth , 14 octets

A.Q|>1fqsTHyG0

Essayez-le en ligne!

Nettoyer , 89 octets

import StdEnv,Data.List,Data.Func
$n=find((==)n o sum)o sortBy(on(>)length)o subsequences

Essayez-le en ligne!

Définit la fonction $ :: Int -> [Int] -> (Maybe [Int])renvoyant Nothings'il n'y a pas de combinaison appropriée d'éléments, et (Just [elements...])sinon.

JavaScript (ES6), 108 octets

Prend l'entrée comme (array)(n). Renvoie un tableau ou false.

a=>n=>a.reduce((a,x)=>[...a,...a.map(y=>1/r[(y=[...y]).push(x)]||eval(y.join`+`)-n?y:r=y)],[[]],r=!n&&[])&&r

Essayez-le en ligne!

Cela a commencé cool et petit, mais les cas de bord m'ont eu. Quoi qu'il arrive, je suis fier du travail que je fais dans ce domaine.

Python 3 , 169 161 161 154 octets

from itertools import*
def f(a,x):
	if sum(a)==x:return a
	try:return[c for i in range(len(a))for c in combinations(a,i)if sum(c)==x][-1]
	except:return 0

Essayez-le en ligne!

R , 100 80 octets

function(a,x){i[sum(a|1):0,j[combn(a,i,,F),if(sum(j)==x)return(j)]]
F}
`[`=`for`

Essayez-le en ligne!

20 octets économisés grâce à digEmAll

Retourne FALSEpour des critères impossibles.

Attaché , 28 octets

${(y&`=@Sum\Radiations@x)@0}

Essayez-le en ligne!

Alternatives

34 octets :f[x,y]:=({y=Sum@_}\Radiations@x)@0

30 octets :First@${y&`=@Sum\Radiations@x}

29 octets :{(_&`=@Sum\_2)@0}#/Radiations

29 octets :${({y=Sum@_}\Radiations@x)@0}

29 octets :`@&0@${y&`=@Sum\Radiations@x}

29 octets :{_}@@${y&`=@Sum\Radiations@x}

Explication

${(y&`=@Sum\Radiations@x)@0}
${                         }    function receiving two arguments, x and y
            Radiations@x        calculate the radiations of x
                                (simulates removing all possible subslices of x)
           \                    keep those radiations
        Sum                     ...whose sum...
     `=@                        ...equals...
   y&                           ...y
  (                     )@0     select the first one (always the longest)

APL (NARS), 65 caractères, 130 octets

{m←⍺=+/¨v←1↓{0=⍴⍵:⊂⍬⋄s,(⊂1⌷⍵),¨s←∇1↓⍵}⍵⋄0=↑⍴b←m/v:⍬⋄b⊃⍨n⍳⌈/n←⍴¨b}

↓ est utilisé car le premier élément de l'ensemble d'ensembles serait un ensemble vide (ici ⍬ Zilde), que l'on veut éliminer car il semble que + / ⍬ soit nul ...

Pour ne pas trouver, ou erreur, il retournerait ⍬ ou en texte imprimé:

  o←⎕fmt
  o ⍬
┌0─┐
│ 0│
└~─┘

tester:

  z←{m←⍺=+/¨v←1↓{0=⍴⍵:⊂⍬⋄s,(⊂1⌷⍵),¨s←∇1↓⍵}⍵⋄0=↑⍴b←m/v:⍬⋄b⊃⍨n⍳⌈/n←⍴¨b}

  o 1 z ,1
┌1─┐
│ 1│
└~─┘
  o 2 z ,1
┌0─┐
│ 0│
└~─┘
  o 10 z 1 2 3 4 5 6 7 8 9 10
┌4───────┐
│ 1 2 3 4│
└~───────┘
  o 10 z 2,2,2,2,2,2,2,2,2
┌5─────────┐
│ 2 2 2 2 2│
└~─────────┘
  o ¯8 z 2,2,2,2,¯2,¯2,¯2,¯4,¯2
┌7──────────────────┐
│ 2 2 ¯2 ¯2 ¯2 ¯4 ¯2│
└~──────────────────┘
  o ¯6 z ¯2,¯4,¯2
┌2─────┐
│ ¯4 ¯2│
└~─────┘
  o 0 z 2,2,2,4,2,¯2,¯2,¯2,¯4,¯2
┌10───────────────────────┐
│ 2 2 2 4 2 ¯2 ¯2 ¯2 ¯4 ¯2│
└~────────────────────────┘
  o 10 z 1 2 3 4
┌4───────┐
│ 1 2 3 4│
└~───────┘
  o 10 z 1 2 3
┌0─┐
│ 0│
└~─┘
  o 0 z ⍬
┌0─┐
│ 0│
└~─┘
  o +/⍬  
0
~