# Sum of Numbers of Array [closed]

Given an array (N) of integers, check if it is possible to obtain a sum of S, by choosing some (or none) elements of the array and adding them.

Example #1

{1,2,3}
4


should output

1 (or true)


because 1 and 3 can be added to produce 4.

Example #2

{3,6,2}
0


should output

1 (or true)


because adding none of them together produces 0.

Example #3

{0,4,3,8,1}
6


should output

0 (or false)


because no combination of the elements in the array can be added to produce 6.

Example #4

{3, 2 ,0 ,7 ,-1}
8


should output

1


because 2+7+(-1)=8

• Which criterion is it? You can't have more than one. – Kendall Frey Jan 8 '14 at 14:58
• You wrote check if it is possible to obtain a sum of S. What's S? Is that the array? If it's the array, then you can always obtain a sum from it, because you said that it's an array of integers. – ProgramFOX Jan 8 '14 at 15:08
• This is the subset sum problem, but I think it's just about sufficiently different from the existing subset sum question to not count as a duplicate. – Peter Taylor Jan 8 '14 at 15:27
• Well the examples certainly helped (I was halfway through a linear combination solution) – user11485 Jan 8 '14 at 16:08
• I think popularity contest is a bad fit for this question personally. – Tim Seguine Jan 8 '14 at 17:45

## Mathematica

This is easy in Mathematica. (1) Generate the subsets of your input list, using the Subsets[] command (I had originally used Permutations[], which works but produces redundant results), (2) sum the numbers in each subset by mapping the Total[] command across the list of subsets, then (3) check to see if the target sum S is represented among those sums with MemberQ[]. To be concise, I've shown this below implemented as a single nested command.

Put your inputs in the first line and execute this:

list = {0, 4, 3, 8, 1}; target = 6;
MemberQ[Total /@ Subsets[list], target]


Assuming one-character variable names, that's 28 bytes of code.

• Instead of Permutations, maybe you could use power sets: Subsets[list] but that might only work if the list does not have duplicate values. – Justin Jan 8 '14 at 17:24
• @Quincunx You are correct, using Subsets[list] is clearly better (and causes no problems with duplicate values); I will amend the code and my discussion accordingly. – Michael Stern Jan 8 '14 at 18:18
• Iterating through all subsets of set? Your approach will fail even for 50 elements array. Using Mathematica application for that sounds like sarcasm! – SergeyS Jan 8 '14 at 19:38
• @SergeyS Why will it fail? 2**50 sets is too many sets for Mathematica? – Justin Jan 10 '14 at 18:57
• @Quincunx - 2**50 is too large number of sets to iterate through. It will take years on personal computer. – SergeyS Jan 10 '14 at 19:56

## C#, complexity O(N*R)

I think this is the first not-exponential solution so far. Complexity - O(N * R); Space - O(R) bytes; where N is length of input array, and R is the difference between sum of positive numbers and sum of negative numbers in array.

On my machine it takes about 15 seconds calculating answer for input array with 1000 randomly generated integers in range [-10000..10000]

static bool HasSum(int[] a, int s)
{
int n = a.Length;
int positiveSum = a.Where(i => i > 0).Sum();
int negativeSum = a.Where(i => i < 0).Sum();
if (s > positiveSum || s < negativeSum)
return false;
int offset = -negativeSum;
s += offset;
int r = positiveSum - negativeSum + 1;
bool[] map = new bool[r];
map[offset] = true;
for (int i = 0; i < n; i++)
if (a[i] < 0)
{
for (int j = 0; j < r; j++)
if (map[j])
map[j + a[i]] = true;
}
else
{
for (int j = r - 1; j >= 0; j--)
if (map[j])
map[j + a[i]] = true;
}
return map[s];
}


## Python

Much like the ruby solution.

def f(l, s):
if s == 0: return True
if l == []: return False
return f(l[1:], s) or f(l[1:], s - l[0])

l = list(input())
s = int(input())
print f(l, s)


Input format:

[1,2,3]
4


to stdin.

• and this works... I blame my ruby 2.2 dev version (well I have the less effective algorithm now...) – user11485 Jan 8 '14 at 22:25
• Good looking one liner: return s == 0 or l != [] and (f(l[1:], s) or f(l[1:], s - l[0])) – ThinkChaos Jan 9 '14 at 13:24

# Ruby - the recursive brute force is the best brute force

def subsetSum(n,s)
n.sort!  #ruby checks if the array is already sorted, which doesn't take long
return true if (s==0) || n.include?(s)  #pretty sure this gets cached
if n[-1] > s  #(optional, will fail in some scenarios with negatives)
n.delete_at(-1)  #remove last number if it's over S
return subsetSum(n,s)
end
if n.length>0
t=n.delete_at(n.length - 1) #length for safety
return true if subsetSum(n,s-t)
return true if subsetSum(n,s)  #check with and without the last number used
end
false
end


example usage: subsetSum([2,3,4],7) => true Warning* will fail when negative numbers are used, I need to go right now and will try to fix the issue later.

# Alternative solution (unoptimized brute force)

def subsetSum(n,s)
return true if s==0
(0..n.length).each{|x|
n.combination(x).each{|y|
return true if y.inject(:+) == s
}
}
return false
end


(this one fully works, but is less effective)

• I appreciate the comments, but this style of leaving no space between code and comment is not too popular among me… – manatwork Jan 8 '14 at 16:14
• @manatwork better? – user11485 Jan 8 '14 at 16:17
• Much better. :) – manatwork Jan 8 '14 at 16:17
• Which version of Ruby? 1.9.2 protests against your style: “formal argument cannot be a constant”. – manatwork Jan 8 '14 at 16:25
• Also some typos: include? (no final “s”), extra “]” in the last subsetSum() call's parameters, either && instead of or, or put the expression in parenthesis. Beside that, seems that fails on example #4. – manatwork Jan 8 '14 at 16:32

# Clojure

Function to generate all sub-sets, then checks if any add up!

(fn [s n]
(let [genfun (fn [s]
(reduce
(fn [init e]
(set (concat init (map #(conj % e) init) [[e]])))
[[]] s))]
(some #(= n %)
(map #(reduce + %) (genfun s)))))


### R, create all possible combinations and their sum

l=lapply;!S|S%in%unlist(l(l(seq_along(N),combn,x=N),colSums))


The command returns TRUE or FALSE.

N and S are variables, e.g., N <- c(1, 2, 3) and S <- 4.

Very simple, just take all the subsets of the input array and check if any of them sum to the given number.

subsets [] = [[]]
subsets (x:xs) = [x] : subsets xs ++ (map (x:) (subsets xs))

f xs n = any ((==n).sum) (subsets xs)


# C# LINQ

f has to be initiated to null before assigning the lambda expression because it is recursive and the compiler will complain about f not being initialised if I try and declare f and assign to it on the same line. e.g

Func<int, int[], int> f = (s, a) => a.Where((n, i) => s == 0 | (s - n) == 0 | f(s - n, a.Where((_, j) => i != j).ToArray()) == 1).Any() ? 1 : 0;


Working program below.

class Program
{
public static void Main()
{
Func<int, int[], int> f = null;
f = (s, a) => a.Where((n, i) => s == 0 | (s - n) == 0 | f(s - n, a.Where((_, j) => i != j).ToArray()) == 1).Any() ? 1 : 0;
Console.WriteLine(f(5, new[] { 2, 2, 9, 1 }));
}
}


import Control.Monad

checkSum :: [Int] -> Int -> Bool
checkSum xs x = elem x . map sum . filter (not . null) . filterM (const [True, False]) $xs  A simpler Haskell formula that makes use of the list monad. The algorithm is broken down below: -- Take the list xs -- Compute the power set of this list filterM (const [True, False]) -- Filter out the empty set from the result filter (not . null) -- Add up each subset of the power set map sum -- Check and see if any of the sums is equal to the value elem x  Rust  fn check(array: &[int], s:int) -> bool{ if s ==0 { return true; } if array == [] { return false; } return (check(array.slice(1, array.len()), s) || check(array.slice(1,array.len()), s - array[0])); } fn main(){ let a = ~[1,2,3]; println!("{}",check(a,0)); }  I just copied quasimodo's solution in rust # Haskell Unlike the most other solutions, by computing the set of all possible sums, we often get better complexity than by constructing the sums of all possible subsets. In particular, if the numbers are small, the size of the set is bounded by t=Σ|nₖ|, so the whole algorithm is O(n t log t). import qualified Data.IntSet as S extend :: S.IntSet -> Int -> S.IntSet extend set n = set S.union (S.map (+ n) set) sums :: [Int] -> S.IntSet sums = foldl extend (S.singleton 0) canSumTo :: Int -> [Int] -> Bool canSumTo s = S.member s . sums  Or as a one-liner (with swapped arguments): canSumTo' :: [Int] -> Int -> Bool canSumTo' = flip S.member . foldl (\set n -> S.union set (S.map (+ n) set)) (S.singleton 0)  ## APL Now that the character count doesn't matter, here's some ungolfed APL: canSumTo ← { ⍝ get all subsets subsets ← { ⍝ the bits for [1..2^length] each form ⍝ a bitmask for a subset bitmasks ← ↓⍉((⍴⍵)/2)⊤⍳2*⍴⍵ ⍝ apply each bitmap to the input /∘⍵¨bitmasks }⍺ ⍝ does any of the subsets of ⍺ sum to ⍵? ⍵ ∊ +/¨subsets }  Then:  1 2 3 canSumTo 4 1 3 6 2 canSumTo 0 1 0 4 3 8 1 canSumTo 6 0 3 2 0 7 ¯1 canSumTo 8 1  • I don't believe I've ever seen ungolfed APL before. – Justin Jan 8 '14 at 22:55 • @Quincunx: well not on this site you wouldn't :) – marinus Jan 9 '14 at 21:41 ## Fortran Algorithm is as follows: 1. Check if the sum of the array is less than S 2. Check if any of the elements of the array equals S 3. Sort array 4. Slice linear elements of array & check if sum of slice is S 5. Sum elements by jumping i spaces I have omitted the module quicksort but it does exactly what it sounds like it does. It passed all the test cases above, but it does fail on the array 0,-1,3,5,7 when asked for 11 (requires cells 1,4,5 (0,3,4 for those stuck on 0-indexes) which can't be done for slicing--I am working on fixing this) program rand_array_sum use quicksort implicit none integer, dimension(:), allocatable :: array integer :: n, s print *,"Enter number of cells in array" read(*,*) n; allocate(array(n)) print *,"Enter comma-separated integers in array:" read(*,*) array print *,"What is the sum you want?" read(*,*) s if(s==0) then print *,1 stop endif if(sum(array)< s) then print *,0 stop endif if(any(array==s)) then print *,1 stop endif call sort(array) print *,"Sorted array:",array call sum_array(n,array,s) contains subroutine sum_array(n,a,s) integer, intent(in) :: n, a(n), s integer :: i, j, b ! linear slices do i=1,n do j=1,i !print '("i=",i0," j=",i0," b=",i0)',i,j,abs(i-j) b=abs(i-j) if(sum(array(j:n-b))==s) then print *,1 return endif enddo print *,"" enddo ! jumping slices do i=2,n do j=1,n-i+1 if(sum(array(j:n:i))==s) then print *,1 return endif enddo enddo ! if all as failed, then it cannot be done print *,0 end subroutine sum_array end program rand_array_sum  # Java golfed (223 chars): int r(int s,int[] a){for(int i=0;i<a.length;i++){if(s==0|(s-a[i])==0|r(s-a[i],s(a,i))==1)return 1;}return 0;} int[] s(int[] a,int k){int[] b=new int[a.length-1];for(int i=0;i<a.length-1;i++){b[i]=a[i+(k>i?0:1)];}return b;}  formatted: class M { public static void main(String[] a) { System.out.println(r(6, new int[] { 0, 4, 2, 8, -1 })); } static int r(int s, int[] a) { for (int i = 0; i < a.length; i++) { if (s == 0 | (s - a[i]) == 0 | r(s - a[i], s(a, i)) == 1) { return 1; } } return 0; } static int[] s(int[] a, int k) { int[] b = new int[a.length - 1]; for (int i = 0; i < a.length - 1; i++) { b[i] = a[i + (k > i ? 0 : 1)]; } return b; } }  • Since this is a popularity-contest, there is no need to show golfed code. Instead, an explanation of how your program works would be better. – Justin Jan 8 '14 at 18:58 • Oh... Sorry about that. – Dean Panayotov Jan 8 '14 at 20:28 # JavaScript An homage to / shameless ripoff of quasimodo's solution. function f(l, s) { var n = l.slice(1) return !s || (!l.length ? false : f(n, s) || f(n, s - l[0])) }  • Apparently I can't upvote his solution or comment on it, so I left an homage instead. ;) – user13957 Jan 8 '14 at 20:43 • You should be able to upvote; it comes at 15 rep. However, commenting everywhere comes at 50 rep. – Justin Jan 8 '14 at 20:56 • @Quincunx I think it's because I'm not a registered user – user13957 Jan 8 '14 at 20:58 • The homage to the solution that uses my algorithm (for some reason broken on ruby 2.2dev). Or some fault of mine (it works fine on python though q-q) – user11485 Jan 8 '14 at 22:26 ### Ruby This is a succinct way to do it in Ruby using Array#combination but has the unfortunate consequence of performing the calculation of all possible combinations of sub-sums in array and then checking to see if the given sum is possible. With a large array, that is likely to be a lot of needless calculation. def contains_sum?(array, sum) [*1..array.size].reduce([]) { |x, i| x + array.combination(i).to_a } .map { |c| c.reduce(:+) }.push(0).include?(sum) end  Here's a version that isn't a one-liner, but tries to avoid calculating more sums than it has to: def contains_sum?(array, sum) return true if sum == 0 || array.include?(sum) [*2..array.size].each do |i| return true if array.combination(i).detect { |c| c.reduce(:+) } == sum end false end  # k/q k){|/y=+/'+x*(-#x)#+0b\:'!*/(#x)#2}  this is an adaptation of the s function from http://kx.com/q/greplin.q s n returns the bitmasks for the power set of a set of count n i then simply apply the mask matrix to the vector, sum them all up and look for the number in question ungolfed and converted back to q, and with the examples: q)s:{neg[x]#flip 0b vs/:til prd x#2} q)f:{any y=sum each flip x*s count x} q)f[1 2 3;4] 1b q)f[3 6 2;0] 1b q)f[0 4 3 8 1;6] 0b q)f[3 2 0 7 -1;8] 1b q)  # Haskell We don't care which sets sum to the value, only whether any exists, so we need not ever compute the power-set, only the sums of the elements of the power-set. In particular, F(S) := { L | L ∈ Power(S) } F(∅) = {0} F(S) = { x + s | sF(Sx) } ⋃ F(Sx) ∀ xS The following recursive definition arises naturally. sums [] = [0] sums (x:t) = sums t >>= \y -> [x+y,y] possible n xs = elem n xs || elem n$ sums xs


possible is a function whose first argument is a target number, and whose second argument is a list (array) to search for the target sum within. I added a test for inclusion before a test for summation, as that both makes the search faster and makes searching of infinite lists containing the target much faster. I might make this more complicated sophisticated later on.

## Edit 1

I found that my code didn't work well for infinite lists *not* containing the target, so I optimized my code to use a scanl, thereby performing a lazy search and increasing the speed of infinite lookups dramatically.

import Data.List

sums :: Integral a => [a] -> [[a]]
sums = scanl (\acc x -> [i + j|j<-[x,0],i<-acc]) [0]

possible :: Integral a => a -> [a] -> Bool
possible n xs = any (elem n) (sums xs)


The order of the binds in the generator matters; switching the order of i and j reduces the performance speed. Also, the order of [x,0] matters, as it ensures that each successive element of the scan will begin with the sums including the new element, instead of starting with the ones already seen. This does not change the speed of advancing in the scan, but it increases the speed of identifying a scan containing the target.