Past exam of the year 1 of the computer science course of the University of Oxford / 2021 / Functional programming, design and analysis of algorithms (resit) / 6

subsetSum(A, s):
    S = sum of A
    if s < 0 or s > S: return false
    D[0..s] = false
    D[0] = true
    for each indexed entry a in A:
        for t from s down to a:
            D[t] = D[t] or D[t-a]
    return D[s]

Descending updates make both right-hand-side values belong to the previous list prefix: when updating

t

, the smaller location

t - a

has not yet been updated for this entry. This prevents using the same occurrence repeatedly. Induction on the list prefix proves the recurrence and the returned answer.

The time is

O (n (s + 1)) \subseteq O (n^{2} k)

for nonempty input with

k \geq 1

, and space is

O (s + 1) \subseteq O (nk)

. More generally one may fill through

S

and answer every target from the same table. For a two-way equal partition, reject odd

S

; otherwise ask for target

S /2

. A selected subset with that sum leaves its complement with the same sum. These are bounds polynomial in the numerical bound

k

; without that bound the method is pseudopolynomial in a binary-encoded unrestricted target.^[ref]

Solution

 0  0

Let

S

again be the total. Reject unless

S

is divisible by three, and put

h = S /3

. Define

D_{i} (x, y)

to mean that the first

i

occurrences can be assigned to three groups so that the first two groups have sums

x

and

y

. Their third sum is already determined by the processed list prefix sum minus

x + y

, so it need not be stored as another coordinate.

Initialize

D_{0} (0, 0)

true and all other states false. For each reachable state, assign the next occurrence to exactly one group:

threeEqualParts(A):
    S = sum of A
    if S mod 3 != 0: return false
    h = S/3
    D[0..h,0..h] = false
    D[0,0] = true
    for each indexed entry a in A:
        Next[0..h,0..h] = false
        for x from 0 to h:
            for y from 0 to h:
                if D[x,y]:
                    Next[x,y] = true
                    if x+a <= h: Next[x+a,y] = true
                    if y+a <= h: Next[x,y+a] = true
        D = Next
    return D[h,h]

The three transitions put the occurrence in the third, first or second group, respectively. Using a fresh layer prevents reusing it. Conversely, deleting the last occurrence from any valid list prefix assignment leaves exactly one predecessor state, so induction proves completeness as well as soundness. At the final state

(h, h)

, the third sum is

S - 2 h = h

, giving precisely the required disjoint partition.

There are

(h + 1)^{2}

states per layer and a constant number of transitions per state. Thus the time is $O (n (h + 1)^{2}) \subseteq O (n^{3} k^{2})$ , and rolling layers use $O ((h + 1)^{2}) \subseteq O (n^{2} k^{2})$ space for nonempty inputs. The source mentions an additional integer

s

in this part, but it does not occur in the stated equal-partition condition; the required target is determined by

S

. Empty groups are allowed by the stated subset formulation.

Past exam of the year 1 of the computer science course of the University of Oxford / 2021 / Functional programming, design and analysis of algorithms (resit) / 6

a

Solution

b

Solution

 Ancestors (10)

 Discussion (0)

 Articles by others on the same topic (0)

Past exam of the year 1 of the computer science course of the University of Oxford / 2021 / Functional programming, design and analysis of algorithms (resit) / 6

a

Solution

b

Solution

 Ancestors (10)

 Discussion (0)  Subscribe (1)

 Articles by others on the same topic (0)

 Discussion (0)