# N-bit Variation on Subset-Sum

For another challenge I am writing, I need to verify that test cases are solveable with bounded integers. Specifically, I need to verify the following, for a non-empty array of integers A and an integer bit width n:

1. All integers a in A satisfy -2**(n-1) <= a < 2**(n-1) (representable with n-bit two's complement integers).
2. The length of A is less than 2**n.
3. The sum of A satisfies -2**(n-1) <= sum(A) < 2**(n-1).
4. All combinations of elements in A satisfy all of the above conditions.

Naturally, I've decided to outsource this problem to you!

Given an array of integers A and a positive integer bit width n, verify that A satisfies the conditions above.

## Test Cases

[0, 0, 0], 2: True
[0, 0, 0, 0], 2: False (violates #2)
[1, 2, 3, 4, 5], 8: True
[1, 2, 3, 4, 5], 2: False (violates all conditions)
[1, 2, 3, 4, 5], 5: True
[-3, 4, 1], 4: True
[10, 0, -10], 4: False (violates #1 and #4)
[27, -59, 20, 6, 10, 53, -21, 16], 8: False (violates #4)
[-34, 56, 41, -4, -14, -54, 30, 38], 16: True
[-38, -1, -11, 127, -35, -47, 28, 89, -8, -12, 77, 55, 75, 75, -80, -22], 7: False (violates #4)
[-123, -85, 6, 121, -5, 12, 52, 31, 64, 0, 6, 101, 128, -72, -123, 12], 12: True


## Reference Implementation (Python 3)

#!/usr/bin/env python3
from itertools import combinations
from ast import literal_eval

def check_sum(L, n):
return -2**(n-1) <= sum(L) < 2**(n-1)

def check_len(L, n):
return len(L) < 2**n

def check_elems(L, n):
return all(-2**(n-1) <= a < 2**(n-1) for a in L)

A = literal_eval(input())
n = int(input())
OUTPUT_STR = "{}, {}: {}".format(A, n, "{}")

if not (check_elems(A, n) and check_len(A, n) and check_sum(A, n)):
print(OUTPUT_STR.format(False))
exit()

for k in range(1, len(A)):
for b in combinations(A, k):
if not check_sum(b, n):
print(OUTPUT_STR.format(False))
exit()

print(OUTPUT_STR.format(True))


Try it online!

• Sandbox – user45941 Dec 13 '17 at 4:02
• Must we handle the empty list? – Mr. Xcoder Dec 14 '17 at 5:18
• @Mr.Xcoder No, I'll clarify. – user45941 Dec 14 '17 at 5:19

# Wolfram Language (Mathematica), 40 bytes

Max[x=2Tr/@Subsets@#,-x-1,Tr[1^#]]<2^#2&


Try it online!

Condition 1 is implied by checking condition 3 for all subsets, including the one-element ones. So we take the max of

• twice the sum of each subset,
• one less than twice the negative of the sum of each subset, and
• the length of the whole set

and check if that's less than 2^#2 (where #2 is the bit-width input).

At the cost of only 6 more bytes, we can replace Subsets@# with GatherBy[#,Arg], which is much more efficient because it computes only the two worst-case subsets: the subset of all nonnegative values, and the subset of all negative values. (This works because Arg has a value of 0 on the former and π on the latter.)

# Jelly, 19 bytes

ŒPS€;⁸L¤ḟ⁹’2*$ŒRṖ¤Ṇ  Try it online! It suffices to check that mapped sum of powerset + length of set is in the required range. • I think (though I am not sure) you can use ÆẸ instead of 2*$ (untested) – Mr. Xcoder Dec 13 '17 at 13:11
• @Mr.Xcoder It does work. – user202729 Dec 14 '17 at 1:00

# 05AB1E, 1312 11 bytes

Saved 1 byte thanks to Mr. Xcoder

æO·D±¹gMIo‹


Try it online!

Explanation

æ             # powerset of first input
O            # sum each subset
·           # multiply each element by 2
D          # duplicate
±         # bitwise negation of each element in the copy
¹g       # push length of first input
M      # get the maximum value on the stack
Io    # push 2**<second input>
‹   # compare

• @Mr.Xcoder: Oh yeah, thanks! (I keep forgetting about ±) – Emigna Dec 13 '17 at 13:12

## JavaScript (ES6), 7563 58 bytes

a=>n=>!a.some(e=>(a.length|2*(e<0?l-=e:u+=e))>>n,u=0,l=-1)


The sum of any subset of a lies between the sums of the negative and nonnegative elements, so checking the two sums suffices for everything except case 2. Edit: Saved 12 17 bytes thanks to @Arnauld.

• Far much better than my naive approach. :-) This could be shortened down to 61 bytes – Arnauld Dec 13 '17 at 11:41
• Actually, we can just process the test within the loop for 56 bytes. – Arnauld Dec 13 '17 at 12:08
• Hacked on ([-2,-1,-2])(3) – l4m2 Dec 13 '17 at 17:44
• @l4m2 Good catch. Suggested fix (57 bytes) – Arnauld Dec 13 '17 at 18:10
• @Arnauld The problem here is that [-2, -2], 3 should be true, no? – Neil Dec 13 '17 at 20:53

# Jelly, 21 20 bytes

»0,«0$S€~2¦Ḥ;LṀ<2*Ɠ¤  Try it online! Linear time complexity solution. Turns out that I over-estimated the time complexity in The Nineteenth Byte, 2017-12-11 13-15-03Z, by user202729 @NewSandboxedPosts "Real" subset sum problem are much harder. This one can be done in linearithmic time... because now I realize sorting the array is completely unnecessary. Explanation: »0,«0$S€~2¦Ḥ;LṀ<2*Ɠ¤    Main link. Example list: [-1, 0, 1]
»0                      Maximize with 0. Get [0, 0, 1]
,                     Pair with
«0$minimize with 0. Get [-1, 0, 0] S€ Sum €ach. Get [1, -1] ~ Inverse ¦ at element 2 2. (list[2] = ~list[2]) Get [-1, 2] Ḥ Unhalve (double, ×2). Get [-2, 4] ; Concatenate with L Length (3). Get [-2, 4, 3] Ṁ Maximum of the list (4). < ¤ Still less than 2 two * raise to the power of Ɠ eval(input())  • Seems that ~2¦ can be ;~. EDIT: Done. – user202729 Dec 13 '17 at 9:39 • @user202729 Wrong. Still, ;~$ will work. – user202729 Dec 13 '17 at 9:45

# JavaScript (ES6), 114 bytes

Takes input in currying syntax (A)(n). Returns a boolean.

A=>n=>!(A.reduce((a,x)=>[...a,...a.map(y=>[x,...y])],[[]]).some(a=>(s=eval(a.join+),s<0?~s:s)>>n-1)|A.length>>n)


### Test cases

let f =

A=>n=>!(A.reduce((a,x)=>[...a,...a.map(y=>[x,...y])],[[]]).some(a=>(s=eval(a.join+),s<0?~s:s)>>n-1)|A.length>>n)

console.log('[Truthy]')
console.log(f([0, 0, 0])(2))
console.log(f([1, 2, 3, 4, 5])(8))
console.log(f([1, 2, 3, 4, 5])(5))
console.log(f([-3, 4, 1])(4))
console.log(f([-34, 56, 41, -4, -14, -54, 30, 38])(16))
console.log(f([-123, -85, 6, 121, -5, 12, 52, 31, 64, 0, 6, 101, 128, -72, -123, 12])(12))

console.log('[Falsy]')
console.log(f([0, 0, 0, 0])(2)) // violates #2
console.log(f([1, 2, 3, 4, 5])(2)) // violates all conditions
console.log(f([10, 0, -10])(4)) // violates #1 and #4
console.log(f([27, -59, 20, 6, 10, 53, -21, 16])(8)) // violates #4
console.log(f([-38, -1, -11, 127, -35, -47, 28, 89, -8, -12, 77, 55, 75, 75, -80, -22])(7)) // violates #4

# Pyth, 20 bytes

>EleS++KyMsMyQmt_dKl


Try it here!

## Clojure, 121 117 bytes

#(let[l(int(Math/pow 2(dec %2)))](every?(set(range(- l)l))(cons(count %)(for[i(vals(group-by pos? %))](apply + i)))))


Well that was a bit dumb, splitting into positive and negative values is a lot better than sorting. Original, but surprisingly not much longer:

#(let[l(int(Math/pow 2(dec %2)))S(sort %)R reductions](every?(set(range(- l)l))(concat[(count S)](R + S)(R +(into()S)))))


This works by checking prefix sums of the sequence in ascending and descending order, I think it isn't necessary to generate all combinations of elements in A.

(into () S) is in effect same as (reverse S), as lists grow from the head. I couldn't figure out a way to use cons instead of concat when there are two lists to cons to. :/

# Jelly, 15 bytes

ŒPS€Ḥ;~$;LṀl2<Ɠ  Try it online! ### Explanation ŒPS€Ḥ;~$;LṀl2<Ɠ ~ Monadic full program.

ŒP              ~ Powerset.
S€            ~ The sum of each subset.
Ḥ           ~ Double (element-wise).
;~\$        ~ Append the list of their bitwise complements.
;L      ~ Append the length of the first input.
Ṁ     ~ And get the maximum.
l2   ~ Base-2 logarithm.
<Ɠ ~ Is smaller than the second input (from stdin)?


Saved 1 byte thanks to caird coinheringaahing (reading the second input from STDIN instead of CLA).

# Husk, 14 bytes

≥Lḋ▲ṁ§eLöa→DΣṖ


Going with brute force by looping over all sublists, since splitting into positive and negative parts takes more bytes. Try it online!

## Explanation

≥Lḋ▲ṁ§eLöa→DΣṖ  Implicit inputs, say A=[1,2,3,4,5] and n=5
Ṗ  Powerset of A: [[],[1],[2],[1,2],..,[1,2,3,4,5]]
ṁ           Map and concatenate:
Argument: a sublist, say S=[1,3,4]
Σ     Sum: 8
D      Double: 16
→       Increment: 17
öa        Absolute value: 17
§eL          Pair with length of S: [3,17]
Result is [0,1,1,3,1,5,2,7,..,5,31]
▲            Maximum: 31
ḋ             Convert to binary: [1,1,1,1,1]
L              Length: 5
≥               Is it at most n: 1


# Python 2, 7271 70 bytes

def f(x,n):t=2*sum(k*(k<0)for k in x);max(2*sum(x)-t,~t,len(x))>>n>0>_


Output is via presence/absence of an error.

Try it online!