Sum of Numbers of Array [closed]

Question

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

Answer 1

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.

Answer 2

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];
}

Answer 3

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.

Answer 4

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)

Answer 5

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

Answer 6

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.

Answer 7

Haskell

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)

Answer 8

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 }));
    }
}

Answer 9

Haskell

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

Answer 10

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

Answer 11

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)
    

Answer 12

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

Answer 13

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

Answer 14

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;
    }

}

Answer 15

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

Answer 16

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

Answer 17

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)

Answer 18

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 | s ∈ F(S∖ x) } ⋃ F(S∖ x)   ∀ x ∈ S

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.