串S=""(空串)，子串數目只有1種:""

同樣，當S="A"，子串有"A"和""兩個

當S="AB"，子串有"A""B""AB"""

當S="ABC"子串有"A""B""C""AB""AC""BC""ABC"""

S="ABC"其實就是S[]={"A","B","C","\0"}

引入排列組合中的運算子C(N,M)，表示從M個元素中抽其中N個組成一起

計算:C(N,M)=M!/(N!(M-N)!),其中N!=N*(N-1)*(N-2)*...*1

設S="ABC"為3個元素(不計結束符\0)，則非空子集(\0)有

C(1,3)=3:"A""B""C"

C(2,3)=3:"AB""AC""BC"

C(3,3)=1:"ABC"

所以當S有1個字母時子集有1+1(空集)=2

S有2個字母時子集有C(1,2)+C(2,2)+1(空集)=2+1+1=4

S有3個字母時子集有C(1,3)+C(2,3)+C(3,3)+1(空集)==3+3+1+1=8

...

S有N個字母時(N不為0）子集有

C(1,N)+C(2,N)+...+C(N,N)+1=(2的N次方-1)+1=2的N次方,表示成2^N

檢驗：

當N=0時表示空串，子集當然只有空串

當N=1時子集有2^1=2,跟上面列舉法舉出的數目相同，正確。

當N=2時子集有2^2=4,正確

......