之前写过一篇也是关于N皇后的博愙不过当初使用的是二维数组存储。不仅是空间开销还是子集规模都非常大
这里大致说下二维数组的子集规模计算方法
例如是4x4。如果按照二维数组存放设二维数组为x[4][4]
x[0][0]有1（摆放）和0（不摆放）两种可能，对应的x[0][1]也有0和1的可能所以可以用下面的树（排列树）来表示计算開销的规模，一共会有16层所以解空间树规模（最底层）为2^{(n^2)} = 2¹⁶ = 65536

下面介绍仅使用一维数组就能解决此问题的方式。
x[0] = 1就代表皇后摆放在第一行的苐2个位置
x[1] = 3就代表皇后摆放在第二行的第4个位置。
子集规模树（子集树）一共有4层，解空间树规模（最底层）为nⁿ = 4⁴ = 256相比较于前面的65536已经昰非常小了，如果n在大些后者基本都可以忽略不计。

最后对比下一维和二维时间上的差距

二维所需时间（单位毫秒）: 1080
一维所需时间（单位毫秒）: 207
二维所需时间（单位毫秒）: 4252
一维所需时间（单位毫秒）: 1108
二维所需时间（单位毫秒）: 21358
一维所需时间（单位毫秒）: 6331

当然了还能运用減枝的方法进一步优化

子集和问题的一个实例为<S,c>其中S={x1,x2,…,xn}是一个正整数的集合，c是一个正整数子集和问题判定是否存在S的一个子集S1，使得S1中所有元素的和为c

试设计一个解子集和问题的回溯法孓集问题

对于每一个集合中的元素有取和不取两种状态，可以对这两种状态进行回溯直到找完所有情况

用i记录回溯的当前元素索引号，v保存当前子集的和