5
\$\begingroup\$

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

\$\endgroup\$
  • 5
    \$\begingroup\$ Which criterion is it? You can't have more than one. \$\endgroup\$ – Kendall Frey Jan 8 '14 at 14:58
  • 2
    \$\begingroup\$ 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. \$\endgroup\$ – ProgramFOX Jan 8 '14 at 15:08
  • 1
    \$\begingroup\$ 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. \$\endgroup\$ – Peter Taylor Jan 8 '14 at 15:27
  • 1
    \$\begingroup\$ Well the examples certainly helped (I was halfway through a linear combination solution) \$\endgroup\$ – user11485 Jan 8 '14 at 16:08
  • 5
    \$\begingroup\$ I think popularity contest is a bad fit for this question personally. \$\endgroup\$ – Tim Seguine Jan 8 '14 at 17:45

18 Answers 18

3
+50
\$\begingroup\$

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.

| improve this answer | |
\$\endgroup\$
  • \$\begingroup\$ Instead of Permutations, maybe you could use power sets: Subsets[list] but that might only work if the list does not have duplicate values. \$\endgroup\$ – Justin Jan 8 '14 at 17:24
  • \$\begingroup\$ @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. \$\endgroup\$ – Michael Stern Jan 8 '14 at 18:18
  • 1
    \$\begingroup\$ Iterating through all subsets of set? Your approach will fail even for 50 elements array. Using Mathematica application for that sounds like sarcasm! \$\endgroup\$ – SergeyS Jan 8 '14 at 19:38
  • \$\begingroup\$ @SergeyS Why will it fail? 2**50 sets is too many sets for Mathematica? \$\endgroup\$ – Justin Jan 10 '14 at 18:57
  • 1
    \$\begingroup\$ @Quincunx - 2**50 is too large number of sets to iterate through. It will take years on personal computer. \$\endgroup\$ – SergeyS Jan 10 '14 at 19:56
3
\$\begingroup\$

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];
}
| improve this answer | |
\$\endgroup\$
2
\$\begingroup\$

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.

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

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)

| improve this answer | |
\$\endgroup\$
  • \$\begingroup\$ I appreciate the comments, but this style of leaving no space between code and comment is not too popular among me… \$\endgroup\$ – manatwork Jan 8 '14 at 16:14
  • \$\begingroup\$ @manatwork better? \$\endgroup\$ – user11485 Jan 8 '14 at 16:17
  • \$\begingroup\$ Much better. :) \$\endgroup\$ – manatwork Jan 8 '14 at 16:17
  • \$\begingroup\$ Which version of Ruby? 1.9.2 protests against your style: “formal argument cannot be a constant”. \$\endgroup\$ – manatwork Jan 8 '14 at 16:25
  • \$\begingroup\$ 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. \$\endgroup\$ – manatwork Jan 8 '14 at 16:32
2
\$\begingroup\$

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)))))
| improve this answer | |
\$\endgroup\$
1
\$\begingroup\$

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.

| improve this answer | |
\$\endgroup\$
1
\$\begingroup\$

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)
| improve this answer | |
\$\endgroup\$
1
\$\begingroup\$

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 }));
    }
}
| improve this answer | |
\$\endgroup\$
1
\$\begingroup\$

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
| improve this answer | |
\$\endgroup\$
1
\$\begingroup\$

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

| improve this answer | |
\$\endgroup\$
1
\$\begingroup\$

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)
    
| improve this answer | |
\$\endgroup\$
0
\$\begingroup\$

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
| improve this answer | |
\$\endgroup\$
  • \$\begingroup\$ I don't believe I've ever seen ungolfed APL before. \$\endgroup\$ – Justin Jan 8 '14 at 22:55
  • \$\begingroup\$ @Quincunx: well not on this site you wouldn't :) \$\endgroup\$ – marinus Jan 9 '14 at 21:41
0
\$\begingroup\$

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
| improve this answer | |
\$\endgroup\$
0
\$\begingroup\$

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

}
| improve this answer | |
\$\endgroup\$
  • \$\begingroup\$ 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. \$\endgroup\$ – Justin Jan 8 '14 at 18:58
  • \$\begingroup\$ Oh... Sorry about that. \$\endgroup\$ – Dean Panayotov Jan 8 '14 at 20:28
0
\$\begingroup\$

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]))
}
| improve this answer | |
\$\endgroup\$
  • \$\begingroup\$ Apparently I can't upvote his solution or comment on it, so I left an homage instead. ;) \$\endgroup\$ – user13957 Jan 8 '14 at 20:43
  • \$\begingroup\$ You should be able to upvote; it comes at 15 rep. However, commenting everywhere comes at 50 rep. \$\endgroup\$ – Justin Jan 8 '14 at 20:56
  • 1
    \$\begingroup\$ @Quincunx I think it's because I'm not a registered user \$\endgroup\$ – user13957 Jan 8 '14 at 20:58
  • \$\begingroup\$ 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) \$\endgroup\$ – user11485 Jan 8 '14 at 22:26
0
\$\begingroup\$

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
| improve this answer | |
\$\endgroup\$
0
\$\begingroup\$

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)
| improve this answer | |
\$\endgroup\$
0
\$\begingroup\$

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.

| improve this answer | |
\$\endgroup\$

Not the answer you're looking for? Browse other questions tagged or ask your own question.