Arya’s Algorithms

  The Disappearing Subset Sums Problem: Why Can’t I Pin This Down? I wanted my first “seriously stuck” blog post to be worthy of the name, so instead of chasing a problem that collapses with a clever trick, I picked one that looked simple, but has enough depth to swallow you whole. The Problem: Given a set of integers { 1 , 2 , … , n } \{1, 2, \dots, n\} , consider all possible subset sums. For which values of n n is it true that every integer from 1 up to the maximum possible sum can be expressed as a subset sum? In other words: if I take all subsets of { 1 , 2 , … , n } \{1,2,\dots,n\} and add their elements, do I get a perfectly “gapless” sequence of sums from 1 up to n ( n + 1 ) 2 \tfrac{n(n+1)}{2} ? Step 1: Falling Into the Trap of Optimism At first glance, I was sure the answer was “always.” Why wouldn’t it be? With small n n , it seems so: For n = 1 n=1 : Subsets = { } , { 1 } \{ \}, \{1\} . Sums = { 0 , 1 } \{0,1\} . Covers 1. Fine. For n = 2 n=2 : Subsets ...