Subset Sum TI Basic Programming

Question

I'm trying to program my TI-83 to do a subset sum search. So, given a list of length N, I want to find all lists of given length L, that sum to a given value V.

This is a little bit different than the regular subset sum problem because I am only searching for subsets of given lengths, not all lengths, and recursion is not necessarily the first choice because I can't call the program I'm working in.

I am able to easily accomplish the task with nested loops, but that is becoming cumbersome for values of L greater than 5. I'm trying for dynamic solutions, but am not getting anywhere.

Really, at this point, I am just trying to get the list references correct, so that's what I'm looking at. Let's go with an example:

L1={p,q,r,s,t,u}

so

N=6

let's look for all subsets of length 3 to keep it relatively short, so L = 3 (6c3 = 20 total outputs).

Ideally the list references that would be searched are:

{1,2,3}
{1,2,4}
{1,2,5}
{1,2,6}
{1,3,4}
{1,3,5}
{1,3,6}
{1,4,5}
{1,4,6}
{1,5,6}
{2,3,4}
{2,3,5}
{2,3,6}
{2,4,5}
{2,4,6}
{2,5,6}
{3,4,5}
{3,4,6}
{3,5,6}
{4,5,6}

Obviously accomplished by:

FOR A,1,N-2
    FOR B,A+1,N-1
        FOR C,B+1,N
            display {A,B,C}
        END
    END
END

I initially sort the data of N descending which allows me to search for criteria that shorten the search, and using FOR loops screws it up a little at different places when I increment the values of A, B and C within the loops.

I am also looking for better dynamic solutions. I've done some research on the web, but I can't seem to adapt what is out there to my particular situation.

Any help would be appreciated. I am trying to keep it brief enough as to not write a novel but explain what I am trying to get at. I can provide more details as needed.

Answer 1

For optimisation, you simply want to skip those sub-trees of the search where you already now they'll exceed the value V. Recursion is the way to go but, since you've already ruled that out, you're going to be best off setting an upper limit on the allowed depths.

I'd go for something like this (for a depth of 3):

N is the total number of array elements.
L is the desired length (3).
V is the desired sum
Y[] is the array
Z is the total

Z = 0
IF Z <= V
  FOR A,1,N-L
    Z = Z + Y[A]
    IF Z <= V
      FOR B,A+1,N-L+1
        Z = Z + Y[B]
        IF Z <= V
          FOR C,B+1,N-L+2
            Z = Z + Y[C]
            IF Z = V
              DISPLAY {A,B,C}
            END
            Z = Z - Y[C]
          END
        END
        Z = Z - Y[B]
      END
    END
    Z = Z - Y[A]
  END
END

Now that's pretty convoluted but it basically check at every stage whether you've already exceed the desired value and refuses to check lower sub-trees as an efficiency measure. It also keeps a running total for the current level so that it doesn't have to do a large number of additions when checking at lower levels. That's the adding and subtracting of the array values against Z.

It's going to get even more complicated when you modify it to handle more depth (by using variables from D to K for 11 levels (more if you're willing to move N and L down to W and X or if TI BASIC allows more than one character in a variable name).

The only other non-recursive way I can think of doing that is to use an array of value groups to emulate recursion with iteration, and that will look only slightly less hairy (although the code should be less nested).