Sum of Products of Subsets

R - 20

Since the OP said:

Side Note: It's okay to post solutions which do not follow the rules if it demonstrates the strengths of your language. It just won't be part of the scoring.

sum(combn(A,k,prod))

Ruby, O(n*k), 70 - 30 = 40 characters

@r={};r=->a,n,k{@r[[a,n,k]]||=k<1?1:n<1?0:r[a,n-=1,k]+a[n]*r[a,n,k-1]}

if the array can be made global and constant (or if we can ask the caller to clean our cache), we can save seven (or thirteen) more characters.

r=->n,k{@r[[n,k]]||=k<1?1:n<1?0:r[n-=1,k]+@a[n]*r[n,k-1]}

without memoisation, we're at 50 characters, but we don't qualify for the bonus:

r->a,n,k{k<1?1:n<1?0:r[a,n-=1,k]+a[n]*r[a,n,k-1]}

Spaced apart:

r = -> a, n, k {
  k<1 ? 1 :
  n<1 ? 0 :
  r[a, n-1, k] + a[n-1] * r[a, n-1, k-1]
}

With memoization, we get to O(n * k * cost_of_memoization). If the key cannot be hashed well, the cost of memoization quickly grows up. However, a key of the form [[?],#,#] can be hashed quite well, at least in theory. Let's also assume that Ruby arrays cache their hashes, so hashing the same array over and over again takes the same time as hashing it once - linear in size. Also, hash table lookup may be assumed constant-time. So, it is safe to assume that the cost of memoization is constant per lookup, and the initial cost for hashing the array is drowned in the rest of the lookup.

here is the iterative approach:

r={};0.upto(k){|k|0.upto(n){|n|r[[n,k]]=k<1?1:n<1?0:r[[n-=1,k]]+a[n]*r[[n,k-1]]}};r[[n,k]]

Yay! I've beaten Daniero's cheating solution