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:


All integers a in A satisfy -2**(n-1) &lt;= a &lt; 2**(n-1) (representable with n-bit two's complement integers).
The length of A is less than 2**n.
The sum of A satisfies -2**(n-1) &lt;= sum(A) &lt; 2**(n-1).
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) &lt;= sum(L) &lt; 2**(n-1)


def check_len(L, n):
  return len(L) &lt; 2**n


def check_elems(L, n):
  return all(-2**(n-1) &lt;= a &lt; 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!
Wolfram Language (Mathematica), 40 bytes

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


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