Tantangan

Misalkan Anda memiliki daftar angka, dan nilai target. Temukan set semua kombinasi angka Anda yang menambahkan hingga nilai target, mengembalikannya sebagai indeks daftar.

Masukan dan keluaran

Input akan mengambil daftar angka (tidak harus unik) dan nomor penjumlahan target. Keluaran akan menjadi satu set daftar yang tidak kosong, masing-masing daftar berisi nilai integer yang sesuai dengan posisi nilai-nilai dalam daftar input asli.

Contohnya

Input: values = [1, 2, 1, 5], target = 8
Output: [ [0,1,3], [1,2,3] ]

Input: values = [4.8, 9.5, 2.7, 11.12, 10], target = 14.8
Output: [ [0,4] ]

Input: values = [7, 8, 9, -10, 20, 27], target = 17
Output: [ [1,2], [0,3,4], [3,5] ]

Input: values = [1, 2, 3], target = 7
Output: [ ]

Mencetak gol

Ini kode-golf , jadi kode terpendek menang!

Sekam , 10 byte

ηλfo=¹ṁ⁰tṖ

1-diindeks. Cobalah online!

Penjelasan

ηλfo=¹ṁ⁰tṖ  Inputs are a number n (explicit, accessed with ¹) and a list x (implicit).
η           Act on the incides of x
 λ          using this function:
         Ṗ   Take all subsets,
        t    remove the first one (the empty subset),
  f          and keep those that satisfy this:
      ṁ⁰      The sum of the corresponding elements of x
   o=¹        equals n.

Ini menggunakan tambahan terbaru untuk Husk, η(bertindak berdasarkan indeks). Idenya adalah yang ηmengambil fungsi urutan yang lebih tinggi α(di sini fungsi lambda inline) dan daftar x, dan memanggil αfungsi pengindeksan x(yang ada ⁰dalam program di atas) dan indeks x. Misalnya, ṁ⁰ambil subset indeks, petakan indeks untuk xmengatasinya dan jumlah hasilnya.

JavaScript (ES6), 96 byte

Mengambil input dalam sintaks currying (list)(target).

a=>s=>a.reduce((b,_,x)=>[...b,...b.map(y=>[...y,x])],[[]]).filter(b=>!b.reduce((p,i)=>p-a[i],s))

Uji kasus

Ini akan gagal pada test case ke-2 jika 4.8 dan 10 ditukar karena kesalahan presisi IEEE 754 - yaitu 14.8 - 4.8 - 10 == 0tetapi 14.8 - 10 - 4.8 != 0. Saya pikir ini baik-baik saja , meskipun mungkin ada referensi yang lebih relevan di suatu tempat di meta.

let f =

a=>s=>a.reduce((b,_,x)=>[...b,...b.map(y=>[...y,x])],[[]]).filter(b=>!b.reduce((p,i)=>p-a[i],s))

console.log(JSON.stringify(f([1, 2, 1, 5])(8)))
console.log(JSON.stringify(f([4.8, 9.5, 2.7, 11.12, 10])(14.8)))
console.log(JSON.stringify(f([7, 8, 9, -10, 20, 27])(17)))
console.log(JSON.stringify(f([1, 2, 3])(7)))

Berkomentar

a => s =>                 // given an array a[] of length N and an integer s
  a.reduce((b, _, x) =>   // step #1: build the powerset of [0, 1, ..., N-1]
    [ ...b,               //   by repeatedly adding to the previous list b[]
      ...b                //   new arrays made of:
      .map(y =>           //     all previous entries stored in y[]
        [...y, x]         //     followed by the new index x
      )                   //   leading to:
    ],                    //   [[]] -> [[],[0]] -> [[],[0],[1],[0,1]] -> ...
    [[]]                  //   we start with a list containing an empty array
  )                       // end of reduce()
  .filter(b =>            // step #2: filter the powerset
    !b.reduce((p, i) =>   //   keeping only entries b
      p - a[i],           //     for which sum(a[i] for i in b)
      s                   //     is equal to s
    )                     //   end of reduce()
  )                       // end of filter()

Python 2 , 110 byte

lambda a,n:[b for b in[[i for i in range(len(a))if j&1<<i]for j in range(2**len(a))]if sum(a[c]for c in b)==n]

Cobalah online!

R , 85 84 byte

function(l,k){N=combn
o={}
for(i in I<-1:sum(l|1))o=c(o,N(I,i,,F)[N(l,i,sum)==k])
o}

Cobalah online!

1-diindeks.

combnbiasanya mengembalikan matrix, tetapi pengaturan simplify=Fmengembalikan listsebaliknya, memungkinkan kami untuk cmenggabungkan semua hasil bersama-sama. combn(I,i,,F)mengembalikan semua kombinasi indeks, dan kami mengambil N(l,i,sum)==ksebagai indeks ke dalam daftar itu untuk menentukan yang mana yang sama k.

J , 32 31 byte

(=1#.t#])<@I.@#t=.1-[:i.&.#.1"0

Cobalah online!

                  1-[:i.&.#.1"0         Make a list of all masks
                                        for the input list. We flip the bits
                                        to turn the unnecessary (0...0)         
                                        into (1...1) that would be missing.
                                        Define it as t.

(=1#.t#])                               Apply the masks, sum and
                                        compare with the target

         <@I.@#                         Turn the matching masks into 
                                        lists of indices

Japt , 14 byte

m, à f_x!gU ¥V

Uji secara online!

Bagaimana itu bekerja

m, à f_x!gU ¥V   Implicit: U = input array, V = target sum
m,               Turn U into a range [0, 1, ..., U.length - 1].
   à             Generate all combinations of this range.
     f_          Filter to only the combinations where
       x           the sum of
        !gU        the items at these indices in U
            ¥V     equals the target sum.
                 Implicit: output result of last expression

Bersih , 104 102 98 byte

import StdEnv
@n=[[]:[[i:b]\\i<-[0..n-1],b<- @i]]
?l n=[e\\e<-tl(@(length l))|sum(map((!!)l)e)==n]

Cobalah online!

Haskell , 76 byte

x#t=[i|i<-tail$concat<$>mapM(\z->[[],[z]])[0..length x-1],t==sum[x!!k|k<-i]]

Cobalah online!

Jelly , 11 byte

ị³S=
JŒPçÐf

Cobalah online!

1-diindeks. 4 byte yang dihabiskan untuk mengembalikan indeks daripada hanya elemen itu sendiri.

Terima kasih -1 byte ke user202729
-1 byte terima kasih kepada Jonathan Allan

Bahasa Wolfram (Mathematica) , 43 byte

1-diindeks.

Pick[s=Subsets;s@Range@Tr[1^#],Tr/@s@#,#2]&

Cobalah online!

Python 3 , 144 byte

lambda a,t:[[e for e,_ in x]for r in range(len(a))for x in combinations(list(enumerate(a)),r+1)if sum(y for _,y in x)==t]
from itertools import*

Cobalah online!

Diindeks 0. 44 byte dihabiskan untuk mengembalikan indeks daripada hanya elemen itu sendiri.

Brachylog , 18 15 byte

hiᶠ⊇Shᵐ+~t?∧Stᵐ

Cobalah online!

-3 byte karena sekarang berfungsi sebagai generator . (Mungkin dimungkinkan untuk bermain golf lebih banyak, tetapi mengatasi kebutuhan untuk menggunakan indeks adalah canggung.)

    S              The variable S
   ⊇               is a sublist of
  ᶠ                the list of all
 i                 pairs [element, index] from
h                  the first element of
                   the input;
     hᵐ            the first elements of each pair
       +           add up to
        ~t         the last element of
          ?        the input
           ∧       which isn't necessarily
            S      S,
             tᵐ    from which the last elements of each pair
                   are output.

Perl 6 , 45 byte

->\a,\b{grep {a[$_].sum==b},^a .combinations}

Menguji

Diperluas:

->
  \a, # input list
  \b, # input target
{

  grep

  {
      a[ $_ ].sum # use the list under test as indexes into ｢a｣
    ==
      b
  },

  ^a              # Range upto ｢a｣ (uses ｢a｣ as a number)
  .combinations   # get all of the combinations
}

APL (NARS), 49 karakter, 98 byte

{∨/b←⍺=+/¨{∊⍵⊂w}¨n←{⍵⊤⍨k⍴2}¨⍳¯1+2*k←≢w←⍵:⍸¨b/n⋄⍬}

1-diindeks; uji:

  f←{∨/b←⍺=+/¨{∊⍵⊂w}¨n←{⍵⊤⍨k⍴2}¨⍳¯1+2*k←≢w←⍵:⍸¨b/n⋄⍬}
  ⎕fmt 8 f 1 2 1 5
┌2──────────────┐
│┌3────┐ ┌3────┐│
││2 3 4│ │1 2 4││
│└~────┘ └~────┘2
└∊──────────────┘
  ⎕fmt   14.8  f  4.8 9.5 2.7 11.12 10
┌1────┐
│┌2──┐│
││1 5││
│└~──┘2
└∊────┘
  ⎕fmt 17 f 7, 8, 9, ¯10, 20, 27
┌3──────────────────┐
│┌2──┐ ┌2──┐ ┌3────┐│
││4 6│ │2 3│ │1 4 5││
│└~──┘ └~──┘ └~────┘2
└∊──────────────────┘
  ⎕fmt 7 f 1 2 3
┌0┐
│0│
└~┘

komentar:

{∨/b←⍺=+/¨{∊⍵⊂w}¨n←{⍵⊤⍨k⍴2}¨⍳¯1+2*k←≢w←⍵:⍸¨b/n⋄⍬}
                             ⍳¯1+2*k←≢w←⍵         copy ⍵ in w, len(⍵) in k, return 1..2^(k-1) 
                 n←{⍵⊤⍨k⍴2}¨                     traslate in binary each element of  1..2^(k-1) and assign the result to n
          {∊⍵⊂w}¨                                for each binary element of n return the elemets of ⍵ in the place where there are the 1s
    b←⍺=+/¨                                       sum them and see if the sum is ⍺, that binary array saved in b
  ∨/                                     :⍸¨b/n   if or/b, get all the elements of n that are 1s for array b, and calculate each all indexs
                                               ⋄⍬ else return Zilde as void set

Pyth, 11 byte

fqvzs@LQTyU

Coba online di sini , atau verifikasi semua uji sekaligus di sini .

fqvzs@LQTyUQ   Implicit: Q=input 1 (list of numbers), z=input 2 (target value, as string)
               Trailing Q inferred
          UQ   Generate range [0-<length of Q>)
         y     Powerset of the above
f              Keep elements of the above, as T, when the following is truthy:
      L T        Map elements of T...
     @ Q         ... to the indicies in Q
    s            Take the sum
 q               Is the above equal to...
  vz             z as an integer
               Implicit print of the remaining results