Subset Sum in Ada

Question

One of my favorite classic programming exercises is the Subset Sum problem. I'm (trying) to learn Ada and it's the first thing I wanted to implement, even before a Hello World.

The Subset Sum problem aims to find within a set of numbers, if a specified sum can be found by combining any number of elements from the set. For example, {2, 8, 4} has subset sums of 2, 8, 4, 10 (2+8), 6 (2+4), 12 (8+4), and 14 (2+8+4). The goal of this algorithm is to feed it a set and a sum and determine if the sum is a subset sum or not.

Here's my code:

with Ada.Text_IO; use Ada.Text_IO;
with Ada.Command_line; use Ada.Command_Line;

procedure Subset_Sum is
    -- a set of numbers to find subset sum on
    type Set is array(0..4) of Integer;
    Arr : Set;

    -- find if subset sum exists in a set
    -- @param Arr - the set to check
    -- @param S - the sum to check against Arr
    -- @param N - for iteration; equals Arr.length
    -- @returns - truth value on whether subset sum exists
    function Find_Subset (Arr : in Set; S, N : in Integer) return Boolean is
    begin
        -- a sum of zero is always possible
        if S = 0 then
            return True;
        -- base case, if surpassed all elements of Set
        elsif N = 0 then
            return False;
        end if;
        -- if last is bigger than sum, ignore and go deeper
        if (Arr(N-1)) > S then
            return Find_Subset(Arr, S, N-1);
        end if;
        -- check including the last
        -- and excluding the last
        return Find_Subset(Arr, S, N-1) 
            or else Find_Subset(Arr, S-Arr(N-1), N-1);
    end Find_Subset;

    -- verifies arguments are correct before continuing
    -- @returns - truth value on whether args valid
    function Verify_Args return Boolean is
    begin
        -- only six arguments allowed
        -- one for sum, five for set
        if Argument_Count /= 6 then
            -- instruct user how to use args
            Put("Invalid arguments."); New_Line;
            Put("Use arguments '<arg1> <args2>'."); New_Line;
            Put("<arg1> is the sum to find, <args2> is space delimited list of 5 numbers.");
            return False;
        end if;
        return True;
    end Verify_Args;

begin
    -- if valid arguments
    if Verify_Args then
        Put("{");
        -- populate Arr with arguments
        for i in 0..4 loop
            Arr(i) := Integer'value(Argument(i+2));
            Put(Integer'Image(Arr(i)));
            if i /= 4 then
                Put(", ");
            end if;
        end loop;
        Put("} ");
        -- determine if a subset sum exists
        if Find_Subset(Arr, Integer'Value(Argument(1)), Arr'Length) = False then
            Put("does not contain subset sum " & Argument(1));
        else
            Put("contains subset sum " & Argument(1));
        end if;
    end if;    
end Subset_Sum;

You can run the code like so:

# save as subset_sum.adb
$ gnatmake subset_sum.adb -o sss
$ ./sss <arg1> <args2>
# <arg1> is the sum to find
# <args2> is space delimited list of numbers of size 5
# eg. ./sss 12 2 8 4 1 5

An example execution and output:

$ ./sss 11 2 8 4 9 1
$ {2, 8, 4, 9, 1} contains subset sum 11

This is the naive approach. In my experience, Subset Sum Problem is studied as part of a unit on dynamic programming. My next step is to implement that but in the interim I wanted to get the handle of Ada.

Answer 1

Much of this review is about style. Style's important, especially in joint projects. It's best if style matches what the community has come to expect.

That said, it'd be natural to start off with an unconstrained array type for Set:

type Set is array (Natural range <>) of Integer;

Naming is important. The function doesn't find a subset (clue: it returns a Boolean).

function Check_For_Subset

Parameter names are important too. They should be written from the point of view of the caller, not from that of the implementer. It's good if they make sense when using named parameter assignment; Check_For_Subset (Of_Set => Arr, Summing_To => 0). Note also, we don't need the N parameter, because the parameter Of_Set carries with it the array bounds, length etc in the form of attributes. Using the attributes adds to the code volume, but improves flexibility, and is pretty-much mandatory when using unconstrained parameters.

  (Of_Set : Set; Summing_To : Integer) return Boolean is
begin

I think I have the intent of the algorithm correct in the code comments.

   --  Check whether the recursion should terminate.
   if Summing_To = 0 then
      --  If the required sum is zero, it would be possible to meet
      --  it by using an empty set, even if the current set isn't
      --  empty.
      return True;

Here we use the attribute 'Length.

   elsif Of_Set'Length = 0 then
      --  Summing_to is non-zero, but there are no further
      --  elements to contribute to it.
      return False;
   end if;

Here we use the attribute 'Last, the last index of the actual parameter.

   if (Of_Set (Of_Set'Last)) > Summing_To then

Of_Set (Of_Set'First .. Of_Set'Last - 1) is a "slice" of the array, extending from the first to the last-but-one element. Note, it's possible for the last index of the slice to be less than the first, which corresponds to an empty slice.

I think there's a problem here if Summing_To is negative! Perhaps it should be a Natural?

      --  If the last element is already bigger than the requirred
      --  sum, it cannot contribute; so ignore it and check the
      --  remainder.
      return Check_For_Subset (Of_Set (Of_Set'First .. Of_Set'Last - 1),
                               Summing_To);
   end if;

And then

   return
     --  We may be able to find a subset by excluding the last
     --  element ..
     Check_For_Subset (Of_Set (Of_Set'First .. Of_Set'Last - 1),
                       Summing_To)
     or else
     --  .. or by taking the last element away from the required
     --  sum, and checking the remainder of the input set (this
     --  effectively *includes* the last element).
     Check_For_Subset (Of_Set (Of_Set'First .. Of_Set'Last - 1),
                       Summing_To - Of_Set(Of_Set'Last));
end Check_For_Subset;

Finally. this declares a Set object with the desired range, to be used by the main program. I do question whether it might be better to arrange for indexing by Positive, which would have eliminated the N - 1's in the original code.

Arr : Set (0 .. 4);

---

I wrote some notes on style in the mid-1990’s, updated (a bit) here.