解説

$N$桁の0からはじまる、$N$ビットのグレイコードを生成し、順に$S$とのxor(排他的論理和)を取ればよいです。
グレイコードはビット演算や再帰で生成可能です。

解答例(Python)