[prev] 89 [next]

Example: Subset Sum (cont)

Alternative approach …

subsetsum2(A,n,k)
(returns true if any subset of A[0..n-1] sums to k; returns false otherwise)

  • if the nth value A[n-1] is part of a solution …
    • then the first n-1 values must sum to k – A[n-1]
  • if the nth value is not part of a solution …
    • then the first n-1 values must sum to k
  • base cases: k=0 (solved by {}); n=0 (unsolvable if k>0) 

subsetsum2(A,n,k):
|  Input  array A, index n, target sum k
|  Output true if some subset of A[0..n-1] sums up to k
|         false otherwise
|
|  if k=0 then
|     return true   // empty set solves this
|  else if n=0 then
|     return false  // no elements => no sums
|  else
|     return subsetsum(A,n-1,k-A[n-1]) or subsetsum(A,n-1,k)
|  end if