Sou um jovem bruxo e tento muito não desperdiçar mana durante meus encontros mágicos.
Eu tenho X magias disponíveis a qualquer momento e cada uma delas tem seu próprio custo de mana Y.
X, Y sendo inteiros positivos estritamente menores que 11.
Como iniciante, meu pool de mana flutua muito (é sempre menor que 11) , e preciso de ajuda para lançar o menor número possível de feitiços (pergaminhos são caros, você sabe) enquanto esvazia minha reserva de mana. Se você não encontrar nenhuma combinação de feitiços que corresponda exatamente ao tamanho da minha reserva de mana, deverá me oferecer a mais próxima (e mais barata).

Eu vim até você e sua infinita sabedoria para me ajudar a me tornar o maior bruxo das trevas. Não ficarei desapontado.

Estilo INPUT (porque estilo é tudo):
Y; abcdef
Y é o tamanho da piscina de mana. (a, b, c, d, e, f) são os feitiços. Existem 6 magias, a primeira custa 'a' mana, a segunda custa custa 'b' mana, etc.

ENTRADA: 4; 1 2 3 3 7 6
Tenho 4 manas disponíveis e 6 feitiços disponíveis. Dois feitiços custam 1 mana, 1 feitiço custa 2 mana, dois feitiços custam 3 mana, etc.

SAÍDA: (3,1)

ENTRADA: 3; 1 3 5 2 10
SAÍDA: (3)

ENTRADA: 8; 4 1 9
SAÍDA: (4,1)

ENTRADA: 4; 1 2 2 3
SAÍDA: (2,2), (1,3)
Você deve produzir todas as combinações de feitiços, mas não há necessidade de distinguir feitiços com o mesmo custo.

O menor encantamento para qualquer máquina que você desejar receberá uma profusão de agradecimento e um chicote de destino.

GolfScript, 55 caracteres

[[]]\{{+}+1$%|}/.@{1$0+{+}*.@>!*100*\,-~}+:s%$0={\s=}+,

Experimente online .

> 4 [1 1 2 3 3 7 6]
[[1 3]]

> 3 [1 3 5 2 10]
[[3]]

> 8 [4 1 9]
[[4 1]]

> 4 [1 2 2 3]
[[2 2] [1 3]]

APL (87)

↑∪m/⍨t=⌊/t←⊃∘⍴¨m←m/⍨t=⌈/t←+/¨m←{a/⍨⊃i≥+/a←k[⍵]}¨⊃,/g,{z/⍨∧/¨2>/¨z←,⍳⍵/⍴k}¨1↓g←⍳⍴k←1↓i←⎕

O formato de entrada é uma lista de APL, onde o primeiro elemento é o pool de mana e o restante dos elementos são os feitiços. A saída tem cada combinação possível de feitiços em uma linha separada.

⎕:    4, 1 2 3 3 7 6
3 1
⎕:    3, 1 3 5 2 10
3
⎕:    8, 4 1 9
1 4
⎕:    4, 1 2 2 3
2 2
3 1

Explicação:

• k←1↓i←⎕: leia uma lista da entrada e armazene-a i. Solte o primeiro elemento (mana) e armazene o restante k.
• 1↓g←⍳⍴k: gere uma lista 1até o tamanho de ke armazene-a g. Largue o primeiro elemento, dando [2..len k].
• {... }¨: Para cada um destes, obtenha os índices de cada combinação única kde comprimento ⍵:
  • z←,⍳⍵/⍴k: obtenha uma ⍵matriz tridimensional de índices de comprimento k, alise-a e armazene-a z.
  • ∧/¨2>/¨: para cada coordenada em cada índice, veja se todas as coordenadas para a Nquinta dimensão são mais altas que as da N-1dimensão.
  • z/⍨: selecione zos elementos para os quais o acima indicado é verdadeiro
• ⊃,/g,: porque o acima não funciona para vetores unidimensionais, adicione gà frente. Agora temos uma lista de listas de listas (por causa do foreach) de todos os índices exclusivos k. Concatene as listas e desclassifique-as (por isso, terminamos com uma lista de listas).
• {... }¨: para cada lista possível de coordenadas, procure a combinação correspondente de valores ke filtre os que são muito caros:
  • a←k[⍵]: procure a combinação atual ke armazene-a a.
  • a/⍨⊃i≥+/a: selecione asomente se o primeiro item em i(pool de mana) for igual ou superior à soma dos elementos de a.
• m←: armazena todas as combinações de feitiços que não excedam o limite de mana m.
• m←m/⍨t=⌈/t←+/¨m: selecione mapenas as combinações cuja soma é igual à soma da combinação mais cara e guarde-a mnovamente.
• m/⍨t=⌊/t←⊃∘⍴¨m: selecione mapenas as combinações cujo comprimento é igual ao comprimento da combinação mais curta.
• ↑∪: remova as duplicatas e converta em uma matriz (para exibir cada combinação em uma linha separada).

Rubi, 114 113 caracteres

x,y=eval gets
(d=0..10).find{|r|d.find{|c|s=y.sort.combination(c).select{|s|s.reduce(:+)==x-r}.uniq
p s if s[0]}}

Entrada: uma matriz de dois elementos da mana do assistente e da lista de feitiços, formatada em JSON de uma linha.

Saída: uma matriz 2D das listas de feitiços, formatadas como JSON de uma linha ou nilse o assistente não puder lançar feitiços.

Eu especialmente amo x,y = eval gets. Tão perigoso e mau, mas tão poderoso e simples. Perfeito para jogar golfe.

Ambos sorte uniqsão necessários. Caso contrário, isso produzirá duplicatas para entrada como [4, [1, 3, 1]]. Eu não estou feliz com isso.

findé um método útil para controlar o fluxo. Seu valor de retorno não é tão útil aqui, no entanto. Em termos de comprimento, é comparável any?, cujo valor de retorno é ainda menos útil.

Exemplos:

> [4, [1, 2, 3, 3, 7, 6]]
# [[1, 3]]
> [3, [1, 3, 5, 2, 10]]
# [[3]]
> [8, [4, 1, 9]]
# [[1, 4]]
> [4, [1, 2, 2, 3]]
# [[1, 3], [2, 2]]
> [4, [5, 6, 7]]
# nil

Haskell (GHC), 172 167 143 chars

import Data.List
import GHC.Exts
f(x:y)=head.groupWith length.last.groupWith sum.filter((<=x).sum).nub$subsequences y
main=interact$show.f.read

Desofuscada:

import Data.List
import GHC.Exts

f (x:xs) = head
         . groupWith length
         . last
         . groupWith sum
         . filter ((<= x) . sum)
         . nub
         $ subsequences xs

main = interact (show . f . read)

• Formato de entrada: lista entre colchetes com mana como mana disponível, cauda como feitiços disponíveis (por exemplo [4,1,2,3,3,7,6]).
• Formato de saída: lista de listas entre colchetes, cada sub-lista representando um conjunto possível de feitiços.

Solução simples: pegue o conjunto de potência da entrada e reduza-o filtrando as combinações para as quais temos mana suficiente, etc.

Mathematica 131

Deve haver maneiras mais curtas, mas é isso que pude inventar.

l=Length;
f[{a_,b_}]:=Select[t=Cases[s=SortBy[Union@Cases[Subsets[b],x_/;0<Tr@x<a+1:>{x,Tr@x}],Last],
{x_,s[[-1,2]]}:> x],l@#==l@t[[1]]&]

f[{4, {1, 2, 3, 7, 6}}]

{{1, 3}}

f[{3, {1, 3, 5, 2, 10}}]

{{3}}

f[{8, {4, 1, 9}}]

{{4, 1}}

f[{4, {1, 2, 2, 3}}]

{{1, 3}, {2, 2}}