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.

• Roland Illig: Could you try to replace the or with or else? If that still compiles, it will make your code a bit faster. The or operator always evaluates both of its operands. The same would apply to and being replaced with and then, if your code contained it.
• gator: I'm still new to Ada but I figured it would still short circuit if the first operand evaluates to false?
• Roland Illig: A workaround for the formatting bug is to add a comment to the end of that line, like Arr'Length) = False then -- ' fix highlighting on Stack Overflow. I've done that regularly when I wrote Perl code, which also confuses most editors.
• Roland Illig: I don't get what you mean by "still", but yes, that would short-circuit the boolean evaluation.
• Simon Wright: Your algorithm needs the input to be sorted-ish (try with (5, 5, 3, 2, 1)); and even then, doesn’t it only check consecutive subsequences?

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.

• gator: Great answer. I tried (albeit not very hard) to find a conventions guide for comments, naming, etc and couldn't find much. Interestingly, NASA provides an Ada guide, which is not surprising due to Ada's widespread use in critical systems like in the DOD, aeronautics, etc. The language I am most familiar with and use the most often is C++, and it seems conventions are project specific. To something like Ada, it's a lot more freedom but I dig there's one specific ruleset to follow.
• Simon Wright: Thanks! Try the Ada Quality and Style Guide - I’ll try to add this to the answer