My array should equal this, but it doesn't!

Question

Given an array of integers a which contains n integers, and a single integer x; remove the fewest amount of elements from a to make the sum of a equal to x. If no combinations of a can form x, return a falsy value.

As pointed out in a comment this is the maximum set with a sum of x, excuse my lesser math brain. I forgot a lot of terms since college.

---

Examples (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] (Unchanged)

f([], 0) = [] (Unchanged Zero-sum Case)

---

Examples (Falsy, any consistent non-array value):

Impossible to Make Case: f([-2,4,6,-8], 3) = falsy (E.G. -1)

Zero Sum Case: f([], non-zero number) = falsy (E.G. -1)

• Note: any value like [-1] cannot be valid for falsy, as it is a potential truthy output.

---

Rules:

• Input may be taken in array form, or as a list of arguments, the last or first being x.
• Output may be any delimited list of integers. E.G. 1\n2\n3\n or [1,2,3].
• Any value can be used as a falsy indicator, other than an array of integers.
• Your code must maximize the size of the end array, order does not matter.
  • E.G. For f([3,2,3],5) both [2,3] and [3,2] are equally valid.
  • E.G. For f([1,1,2],2) you can only return [1,1] as [2] is shorter.
• Both the sum of a and the value of x will be less than 2^32-1 and greater than -2^32-1.
• This is code-golf, lowest byte-count wins.
• If there are multiple subarrays of the same size that are valid, it is not acceptable to output all of them. You must choose a single one and output that one.

---

Let me know if this has been posted, I couldn't find it.

Posts I found like this: Related but closed, ...

Answer 1

Brachylog, 8 bytes

h⊇.+~t?∧

Try it online!

Monthly Brachylog answer. Returns false. if it is not possible.

Explanation

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)

Answer 2

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*

Try it online!

_{-4 bytes, thanks to 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

Try it online!

_{-2 bytes, thanks to Janathan Frech}

Answer 3

05AB1E, 9 bytes

æʒOQ}0ªéθ

Try it online!

Answer 4

Japt -h, 11 bytes

à f_x ¥VÃñl

Try it online!

Answer 5

Pyth, 8 bytes

• 8-byter (Try it!) – Outputs only one possible solution. For unsolvable inputs, it doesn't print anything to STDOUT, which is an empty string, which is technically speaking falsey in Pyth, but writes to STDERR. Thanks to FryAmTheEggman for suggesting this (ignoring STDERR and focusing on the STDOUT output only), thus saving 1 byte.

  efqz`sTy    
  

• 9-byter (Try it!) – Outputs only one possible solution, wrapped in a singleton list as allowed by default (e.g. ([1...10], 10) -> [[1,2,3,4]]; ([], 0) -> [[]]). For unsolvable inputs, it returns [], which is falsey in Pyth.

  >1fqz`sTy
  

• 10-byter (Try it!) – For a clearer output, without using the singleton-list rule and using 0 rather than [] as a falsy value.

  e+0fqz`sTy
  

Explanation

First, the code computes the powerset of the input list (all possible ordered sub-collections thereof). Then, it only keeps those collections whose sum is equal to the input number. It should be noted that the collections are generated from the shortest to the longest, so we focus on the last one. To obtain it:

• The 8-byter simply uses the end built-in, which throws an error, but STDERR can be ignored as per our site rules, the output to STDOUT being an empty string, which is falsy.
• The 9-byter takes the last element, but using the equivalent Python code lst[-1:] in place of lst[-1] to avoid errors from being thrown for unsolvable inputs.
• The 10-byter prepends a 0 to the list of filtered sub-collections, then takes the end of that collection (last element). If the inputs aren't solvable, then 0 is naturally used instead.

Answer 6

Jelly, 7 bytes

ŒPS⁼¥ƇṪ

Try it online!

Output clarified over TIO.

Answer 7

Perl 6, 38 37 bytes

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

Try it online!

Curried function.

Answer 8

Brachylog, 4 bytes

⟨⊇+⟩

Try it online!

Just about equivalent to Fatalize's h⊇.+~t?∧, except a lot shorter, thanks to the predicate composition feature which according to the edit history of the reference was a work in progress until January 8, postdating the answer by over two months. ⟨⊇+⟩ is a sandwich, expanding to {[I,J]∧I⊇.+J∧}, where the braces are in this case irrelevant as the sandwich is on its own line anyhow.

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

A far less dramatic transformation of Fatalize's answer, which uses the same predicates with the same variables but comes out a byte shorter from being organized differently:

Brachylog, 7 bytes

h⊇.&t~+

Try it 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.

(Also, if anyone wants to see something odd, change any of the underscores in the test cases into hyphens.)

Answer 9

Pyth, 14 bytes

A.Q|>1fqsTHyG0

Try it online!

Answer 10

Clean, 89 bytes

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

Try it online!

Defines the function $ :: Int -> [Int] -> (Maybe [Int]) returning Nothing if there is no appropriate combination of elements, and (Just [elements...]) otherwise.

Answer 11

JavaScript (ES6), 108 bytes

Takes input as (array)(n). Returns either an array or 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

Try it online!

Answer 12

This started out cool and small, but edge cases got me. Whatever happens, I'm proud of the work I put into this.

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

Try it online!

Answer 13

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`

Try it online!

20 bytes saved thanks to digEmAll

Returns FALSE for impossible criteria.

Answer 14

Attache, 28 bytes

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

Try it online!

Alternatives

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}

Explanation

${(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)

Answer 15

APL(NARS), 65 chars, 130 bytes

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

↓ is used because the first element of the set of sets would be one void set (here ⍬ Zilde), that one want eliminate because it seems +/⍬ is zero...

For not find, or error it would return ⍬ or in print text:

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

test:

  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
~

Answer 16

Husk, 8 bytes

▲fo=⁰ΣQ²

Try it online!

Brachylog is insane.

Answer 17

Haskell, 68 bytes

import Data.List
f x=find((==x).sum).sortOn(sum.(-1<$)).subsequences

Try it online!

Defines f x a to return Just a subset or Nothing.

The only trick here is that sum.(-1<$) is one byte shorter than (0-).length.