Dada uma matriz de números inteiros aque contém n números inteiros e um único inteiro x; remova a menor quantidade de elementos de apara fazer a soma aigual a x. Se nenhuma combinação de for apossível x, retorne um valor falso.

Como apontado em um comentário, este é o conjunto máximo com uma soma de x , desculpe meu cérebro matemático menor. Eu esqueci muitos termos desde a faculdade.

Exemplos (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] (Inalterado)

f([], 0) = [] (Caso inalterado de soma zero)

Exemplos (Falsy, qualquer valor consistente sem matriz):

Impossível argumentar: f([-2,4,6,-8], 3) = falsy (E.G. -1)

Caso de soma zero: f([], non-zero number) = falsy (E.G. -1)

• Nota: qualquer valor como [-1]não pode ser válido para falsidade, pois é uma saída de verdade em potencial.

Regras:

• A entrada pode ser obtida em forma de matriz ou como uma lista de argumentos, sendo o último ou o primeiro x.
• Saída pode ser qualquer lista delimitada de números inteiros. EG 1\n2\n3\nou [1,2,3].
• Qualquer valor pode ser usado como um indicador falso, além de uma matriz de números inteiros.
• Seu código deve maximizar o tamanho da matriz final, a ordem não importa.
  • EG Para f([3,2,3],5)ambos [2,3]e [3,2]são igualmente válidos.
  • Por exemplo, f([1,1,2],2)você só pode retornar [1,1]como [2]é mais curto.
• A soma ae o valor de xserão menores que 2^32-1e maiores que -2^32-1.
• Isso é código-golfe , vitórias mais baixas na contagem de bytes.
• Se houver vários subarrays do mesmo tamanho que são válidos, é não aceitável para a saída de todos eles. Você deve escolher um único e produzir esse.

Deixe-me saber se isso foi publicado, não foi possível encontrá-lo.

Posts que encontrei assim : relacionados, mas fechados , ...

Braquilog , 8 bytes

h⊇.+~t?∧

Experimente online!

Resposta mensal do Brachylog. Retorna false.se não for possível.

Explicação

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 bytes

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*

Experimente online!

_{-4 bytes, graças a Jonathan Allan}

Python 2 , 108 106 bytes

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

Experimente online!

_{-2 bytes, graças a Janathan Frech}

05AB1E , 9 bytes

æʒOQ}0ªéθ

Experimente online!

Japonês -h , 11 bytes

à f_x ¥VÃñl

Experimente online!

Pitão , 8 bytes

• 8-byter ( Experimente! ) - gera apenas uma solução possível. Para entradas insolúveis, ele não imprime nada em STDOUT, que é uma string vazia, que é tecnicamente falsa em Pyth, mas grava em STDERR. Agradecemos a FryAmTheEggman por sugerir isso (ignorando STDERR e concentrando-se apenas na saída STDOUT), economizando 1 byte.

  efqz`sTy    
  

• 9-byter ( Experimente! ) - gera apenas uma solução possível, agrupada em uma lista de singleton conforme permitido por padrão (por exemplo ([1...10], 10) -> [[1,2,3,4]]; ([], 0) -> [[]]). Para insumos insolúveis, ele retorna [], o que é falsey em Pyth.

  >1fqz`sTy
  

• 10 bytes ( Experimente! ) - Para obter uma saída mais clara, sem usar a regra da lista de singleton e usar em 0vez de []um valor falso.

  e+0fqz`sTy
  

Explicação

Primeiro, o código calcula o conjunto de potência da lista de entrada (todas as possíveis subconjuntos ordenados). Em seguida, ele mantém apenas as coleções cuja soma é igual ao número de entrada. Deve-se notar que as coleções são geradas do menor para o maior, portanto, focamos na última. Para obtê-lo:

• O 8-byter simplesmente usa o final embutido, que gera um erro, mas STDERR pode ser ignorado de acordo com as regras do site, sendo a saída para STDOUT uma string vazia, o que é falso.
• O 9 byter pega o último elemento, mas usa o código Python equivalente lst[-1:]no lugar de lst[-1]para evitar que erros sejam lançados para entradas insolúveis.
• O byter de 10 bytes adiciona um 0 à lista de subcoleções filtradas e leva o final dessa coleção (último elemento). Se as entradas não puderem ser solucionadas, então 0 será usado naturalmente.

Geléia , 7 bytes

ŒPS⁼¥ƇṪ

Experimente online!

Saída esclarecida sobre o TIO.

Perl 6 , 38 37 bytes

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

Experimente online!

Função ao curry.

Braquilog , 4 bytes

⟨⊇+⟩

Experimente online!

Quase equivalente ao Fatalize h⊇.+~t?∧, exceto muito mais curto, graças ao recurso de composição de predicados que, de acordo com o histórico de edição da referência, era um trabalho em andamento até 8 de janeiro, com a resposta em mais de dois meses. ⟨⊇+⟩é um sanduíche , expandindo para {[I,J]∧I⊇.+J∧}, onde os aparelhos são irrelevantes nesse caso, pois o sanduíche está em sua própria linha.

                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]).

Uma transformação muito menos dramática da resposta de Fatalize, que usa os mesmos predicados com as mesmas variáveis, mas sai um byte menor do que ser organizado de maneira diferente:

Braquilog , 7 bytes

h⊇.&t~+

Experimente online!

           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.

(Além disso, se alguém quiser ver algo estranho, altere qualquer um dos sublinhados nos casos de teste para hífens.)

Pitão , 14 bytes

A.Q|>1fqsTHyG0

Experimente online!

Limpo , 89 bytes

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

Experimente online!

Define a função $ :: Int -> [Int] -> (Maybe [Int])retornando Nothingse não houver uma combinação apropriada de elementos e (Just [elements...])caso contrário.

JavaScript (ES6), 108 bytes

Toma entrada como (array)(n). Retorna uma matriz 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

Experimente online!

Isso começou legal e pequeno, mas os casos extremos me pegaram. Aconteça o que acontecer, tenho orgulho do trabalho que coloquei nisso.

Python 3 , 169 161 154 bytes

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

Experimente online!

R , 100 80 bytes

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

Experimente online!

20 bytes salvos graças ao digEmAll

Retorna FALSEpara critérios impossíveis.

Anexo , 28 bytes

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

Experimente online!

Alternativas

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

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

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

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

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

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

Explicação

${(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 caracteres, 130 bytes

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

↓ é usado porque o primeiro elemento do conjunto de conjuntos seria um conjunto nulo (aqui ⍬ Zilde), que se deseja eliminar porque parece que + / ⍬ é zero ...

Para não encontrar, ou erro, ele retornaria ⍬ ou no texto impresso:

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

teste:

  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
~