Pierwsze pytanie tutaj, nie krzycz na mnie, jeśli jest to duplikat lub złe wyzwanie.

Wprowadzenie

Sam pomyślałem o tym wyzwaniu i wydaje się, że jest to dobra podstawowa łamigłówka dla początkujących golfistów. Może także pomóc mi zdecydować, którego języka golfowego muszę się nauczyć.

Wyzwanie

Biorąc pod uwagę tablicę liczb całkowitych mniejszych lub równych n, wyprowadzaj lub zwracaj minimalną liczbę liczb z tablicy, które sumują się dokładnie n.

Możesz napisać funkcję lub pełny program.

Wejście

Możesz bezpiecznie założyć 0 <= n < 2^31.

Weź tablicę lub listę dowolnego rodzaju ( vectordla C ++ lub Java LinkedListsą dozwolone), wraz z nopcjonalnym parametrem length, który określa długość tablicy.

Możesz również wziąć dane wejściowe jako ciąg oddzielony spacjami, oddzielony nprzecinkiem lub spacją:

1 5 7 3 7 3 6 3 2 6 3,10

1 5 7 3 7 3 6 3 2 6 3 10

jeśli to jest łatwiejsze.

Wynik

Wyjdź lub zwróć minimalną liczbę liczb z tablicy, które sumują się dokładnie n. Korzystając z powyższego przykładu:

1 5 7 3 7 3 6 3 2 6 3,10

Twój program powinien wydrukować:

2

ponieważ minimalna liczba liczb, które sumują się 10to 2( 7i 3).

W przypadku braku rozwiązania, wydrukuj lub zwróć albo wartość ujemną, 0„Brak rozwiązania” (choć nie byłoby to mądre), ∞(jak sugerowano), lub dowolną inną wartość fałszowania, z wyjątkiem pustego ciągu.

Przykład wejścia i wyjścia

Wejście:

1 5 7 3 7 3 6 3 2 6 3,10
143 1623 1646 16336 1624 983 122,18102
5 6 9,12

Wynik:

2
3
-1

Punktacja

To jest golf golfowy, więc wygrywa najkrótszy kod w bajtach.

Najlepsza odpowiedź zostanie przyjęta w Boże Narodzenie.

Pyth, 12 11 bajtów

lhafqsTQyEY

Pobiera to njako pierwszy wiersz danych wejściowych i listę w drugim wierszu.

lhafqsTQyEY     (Implicit: Q = 1st line of input; E = 2nd line)
         E      The list
        yE      Powerset (sorted by increasing length; empty set first)
   f            Filter by lambda T:
     sT         sum(T)
    q                  ==
       Q                  Q
   fqSTQyE      Sublists that sum to Q, sorted by increasing length
  a       Y     append an empty array (in case none match)
lh              take the length of the first element (0 for empty array)

Wypróbuj tutaj .

Japt , 30 21 18 bajtów

Okazuje się, że była to znacznie bardziej wydajna metoda. ;)

Uà f_x ¥V} ml n- g

Przetestuj online! (Uwaga: n-zmieniono n@X-Y}na ze względu na kompatybilność)

Pobiera to dane wejściowe w postaci tablicy oddzielonej spacjami lub przecinkami, po której następuje liczba. Dane wyjściowe undefineddla przypadków testowych bez rozwiązań.

Uà f_  x ¥ V} ®   l} n- g
UàfmZ{Zx ==V} mZ{Zl} n- g

            // Implicit: U = input array, V = input integer
Uà fZ{   }  // Generate all possible combinations of U, then filter to only items Z where
Zx ==V      //   the sum of Z is equal to V.
mZ{Zl}      // Map each remaining combination to its length.
n-          // Sort by subtraction; smaller items end up in the front.
g           // Take the first item.
            // Implicit: output last expression

Nie mogę uwierzyć, że nie pomyślałem o tej wersji, kiedy pierwotnie to napisałem ...

Od tego czasu dokonano kilku optymalizacji, które przydają się tutaj:

• A Una początku programu zwykle można pominąć.
• Ãjest skrótem do } .
• n teraz domyślnie porządkuje liczby.

Każdy z nich usuwa bajt, w sumie 15:

à f_x ¥VÃml n g

Przetestuj online!

Mathematica, 73 65 bajtów

Min[Length/@Select[IntegerPartitions[#2,#2,#],Sort@#==Union@#&]]&

Funkcja czysta, zwraca, ∞jeśli nie ma rozwiązania.

Python 3, 128 bajtów

To nie jest tak golfa, jak bym chciał, ale popracuję nad tym później.

from itertools import*
def s(a,n):
 for i in range(len(a)):
  for j in permutations(a,i+1):
   if sum(j)==n:return i+1
 return 0

Mathematica, 45 bajtów

Min@Cases[Subsets@#,i_/;Tr@i==12:>Length@#2]&

CJam, 34 bajty

0q~_,2,m*\f.*{:+1$=},\;0f-{,}$0=,+

Wypróbuj online . Format wejściowy to suma, po której następuje lista wartości, np .:

18102 [143 1623 1646 16336 1624 983 122]

Pamiętaj, że spowoduje to wyjątek, jeśli nie zostanie znalezione rozwiązanie. Wyjątkiem jest stderr, gdy CJam jest uruchamiany z wiersza poleceń, a poprawny wynik (0 ) jest nadal wypisywany na standardowe wyjście. Jest to więc zgodne z konsensusem ustalonym w Czy należy dopuścić, aby przedłożenie zakończyło się błędem?

Kod może wyglądać dłużej, niż można się spodziewać. Głównym powodem jest to, że CJam nie ma wbudowanego generowania kombinacji. A przynajmniej taka jest moja wymówka i trzymam się jej.

Wyjaśnienie:

0       Push 0 result for exception case.
q~      Get and interpret input.
_,      Copy and get length of input value list.
2,      Push [0 1].
m*      Cartesian power. This generates all possible lists of 0/1 values with the
        same length as the input value list.
\       Swap input value list to top.
f.*     Apply element-wise product of input value list with all 0/1 lists.
        We now have all combinations of values, with 0 in place of unused values.
{       Start filter block.
  :+      Sum values.
  1$      Copy target sum to top.
  =       Compare.
},      Filter.
\;      Swap target sum to top and discard.
0f-     Remove 0 values. We now have all solution lists.
{,}$    Sort by length.
0=      Get first solution, which after sorting is the shortest.
        This will raise an exception if the list of solutions is empty, bailing
        out with the initial 0 on the stack.
,       Get length of solution.
+       Add the 0 we initially pushed for the exception case.

JavaScript (ES6), 84 bajtów

f=(a,n,m=1e999,x)=>n&&a.map((v,i)=>(x=[...a],x.splice(i,1),x=f(x,n-v)+1)<m?m=x:0)&&m

Wyjaśnienie

Trwa Array od Numbers, a Numberjako argumenty. Zwraca liczbę, Infinityjeśli nie ma wyniku. Jest to funkcja rekurencyjna, która odejmuje ni usuwa każdy element z tablicy jeden po drugim do n == 0.

f=(a,n,m=1e999,x)=> // m and x are not passed, they are here to declare them in the local
                    //     scope instead of globally, initialise m to Infinity
  n&&               // if n == 0, return 0
  a.map((v,i)=>     // iterate over each number in a
    (x=[...a],      // x = copy of a
    x.splice(i,1),  // remove the added number from the array
    x=f(x,n-v)+1)   // x = result for the numbers in this array
      <m?m=x:0      // set m to minimum result
  )
  &&m               // return m

Test

Ten zestaw testów m na Infinitypóźniej zamiast jako domyślny argument, aby działał w Chrome (zamiast tylko Firefox).

var solution = f=(a,n,m,x)=>n&&a.map((v,i)=>(x=[...a],x.splice(i,1),x=f(x,n-v)+1)<m?m=x:0,m=1e999)&&m

Array (space-delimited) = <input type="text" id="array" value="143 1623 1646 16336 1624 983 122" /><br />
n = <input type="number" id="N" value="18102" /><br />
<button onclick="result.textContent=solution(array.value.split` `,N.value)">Go</button>
<pre id="result"></pre>

Haskell, 72 bajty

import Data.List
n#l=head$sort[length x|x<-subsequences l,sum x==n]++[0]

Zwraca, 0jeśli nie ma rozwiązania.

Przykład użycia: 10 # [1,5,7,3,7,3,6,3,2,6,3] -> 2.

Znajdź wszystkie podlisty listy wejściowej, lktóre mają sumęn . Weź długość każdej takiej podlisty i sortuj. Dołącz a0 i weź pierwszy element.

Jeśli lista Singleton jest dozwolone na wyjściu, np [2], możemy zaoszczędzić 7 bajtów: n#l=minimum[length x|x<-subsequences l,sum x==n]. W przypadku braku rozwiązania []zwracana jest pusta lista .