这是呈呈给面试选的一道算法题，当时看到题目的时候，想了一下，猜测是要用递归来做，但一时没有找到突破口，然后就看了看其他人的思路，思考了一下，也用递归的方式做出来了。后来想到递归都可以转化为非递归，于是就试着去做，结果花了两天时间才做出来….
求子集
题目描述：求一个int数组的所有子集，例如：nums=[1,2,3]，则结果为[[1],[2],[3],[1,2],[1,3][2,3],[1,2,3],[]]，解法分为递归和非递归。
递归
首先想想为何这道算法为何可以使用递归去解：求一个int数组的所有子集，就是去任意组合该数组里的元素。而如何才能找到所有的组合，不重复，不遗漏，那么就需要用到循环。例如nums=[1,2,3]，用temp去记录临时的元素组合，初始为空，用result去保存每一个子集元素。那么，我们遍历数组nums，取出元素“1”，放入temp中，这是第一个子集，然后将temp放入result，再看看temp=[1]的这个数组还能和哪些元素组合。这时需要遍历剩下的元素[2,3]，取出“2”，放入temp中，这时temp为[1,2]，放入result中，然后就是寻找temp=[1,2]能组合的元素，就只剩“3”了。当把temp=[1,2,3]加入result之后，就要回到前面temp=[1]的循环，取出“2”后面的元素“3”了，看temp=[1,3]能与那些元素组合，照此方式循环下去。那么递归的思想就出来了，步骤如下：
1. 把当前的temp0加入result中，遍历剩余元素能与temp0组合的子集；
2. 将下一个元素nums[i]加入temp0，得到temp1；
3. 递归，将temp1加入result，遍历寻找剩余元素能与temp1组合的元素；
4. 将temp0中刚加入的nums[i]移除，以便下次循环加入nums[i+1]；
感觉递归的思想解释没那么容易讲清楚，如果画图理解估计就容易理解多了，这里总结一下就是：把当前temp与剩下的元素循环组合(剩下的元素指在nums数组中在temp最后一个元素后面的元素，例如temp=[2]，剩下的元素就是“3”)，而组合的新的temp又会和剩下的元素循环组合，递归在此。
不管上面的思想是否能看到，来看代码：
public void solution1(List<List<Integer>> result, List<Integer> temp,int [] nums, int start){
result.add(new ArrayList<Integer>(temp));
for(int i = start; i < nums.length; i++){
temp.add(nums[i]);
solution1(result, temp, nums, i + 1);
temp.remove(temp.size() - 1);
}
}
用递归的方式求子集真的很简单，代码就那么几行，需要注意的是result加入temp的复制，这是因为temp是对象，是引用传递，如果直接加入到result中，后面的修改会对已加入的temp产生同样的效果。
非递归
之前听大神说过递归都可以转为非递归，而且方法比较简单。我也查了网上的资料，就说递归就是依靠栈来保存当前的状态，一层一层递归下去。那么递归转非递归就只需要借助栈来保存这些状态，通过循环来解决递归。思想是很简单，也很正确，但是实践却不一定很容易。
因为原来的递归里本身就存在for循环，那么非递归肯定是双重循环了。开头是对了，但是结果第一版代码里没有用到栈，结果肯定是错误的。后来把栈加上，并且声明了两个栈，一个用来记录temp，一个用来记录for循环的i。然后我在循环上纠结了好久：for-while-for、while-for、for-for…真的在这个上面思考了很久，还有while上的条件。之前有一版代码，我测试以为通过了，于是贴到题目下面提交，结果就GG了。因为没保留当时的代码，只记得原因是我把第一层循环单独写了出来，造成了有一些子集无法被循环到。后来我就仔细观察递归打印出来的子集结果，我发现当循环到nums最后一个元素后，都会减去temp后两个元素后再加入新的元素（nums元素数量大于2），例如：nums=[1,2,3,4]，子集中[1,2,3,4]后面加入的就是[1,2,4]，就是说在加入temp=[1,2,3,4]之后，就会把temp中的后两位去掉，即“3”和“4”，然后再加入“4”，得到[1,2,4]。如果我把每一步temp都加入到栈里，在我循环到最后一个元素后，只需要进行两次出栈，然后获得栈顶的元素，就可以获得下一个要循环的组合。然后就是循环的下标i，因为存temp的栈弹出了两次，那么存i的栈肯定也要弹两次，但是我们要取的值并不是栈顶的元素，而是第二次弹出的元素+1。如何理解，举个例子：temp=[1,2,3,4,5]，此时栈里存的i为：4，3，2，1，0（由栈顶到栈底）。出栈两次之后temp为[1,2,3]，因为“4”已经循环过了，这时要加入到temp的为“5”，对应的i为4，即第二次出栈的3+1。为什么不直接取栈顶的4？因为循环的结束时栈顶永远是i=4。而temp=[1,2,5]时，存i的栈中存的是4，1，0，而下次循环的时候，temp就由[1,3]开始了。代码如下：
public void solution2(List<List<Integer>> result, int [] nums){
Stack<List<Integer>> stackList = new Stack<List<Integer>>();
Stack<Integer> stackN = new Stack<Integer>();
List<Integer> temp = new ArrayList<Integer>();
stackN.push(0);
stackList.push(new ArrayList<Integer>(temp));
result.add(new ArrayList<Integer>(temp));
int start = 0;
while (!stackN.isEmpty()){
for(int i = start; i < nums.length; i++){
temp.add(nums[i]);
result.add(new ArrayList<Integer>(temp));
stackList.push(new ArrayList<Integer>(temp));
stackN.push(i);
}
stackN.pop();
start = stackN.pop() + 1;
stackList.pop();
stackList.pop();
if (!stackList.isEmpty()){
temp = new ArrayList<Integer>(stackList.peek());
}
}
}
代码是没有经过优化的，我也只是找出了递归的结果的规律，跳出循环的结果为存i的stackN栈为空，而在一开始就加入“0”，是为了防止循环中temp为空对象时，stackN出栈了所有循环中的入栈的i而终止while，而当temp中只有nums中的最后一个元素时，stackN只会入栈一次，但还是会出栈两次，这样就跳出了循环。
在自己将递归转变为非递归的过程中，因为前面的毫无头绪，因此也查了一些非递归求子集的方法，有一种方法的思想非常nice，我分享一下java版的该方法实现：
public void solution3(List<List<Integer>> result, int [] nums){
int length = nums.length;
int size = (int) Math.pow(2, length);
for (int i = 0; i < size; i++){
result.add(new ArrayList<Integer>());
}
for (int i = 0; i < length; i++){
for (int j = 0; j < size; j++){
int n = (j >> i) & 1;
if(n == 1){
result.get(j).add(nums[i]);
}
}
}
}
可以看到上面的代码非常简单，但也通过非递归的方法实现了求子集的要求。首先，假设一个数组的长度为n，则其子集的个数为2^n。这是一个数学结论，我不会证明，但很容易理解：当我们给一个数组增加一个元素的时候，这个元素可以和该数组之前的每一个子集组合，假设之前的个数为n，这现在数组的子集个数就扩大的一倍，即n*2。因为n=1时，即数组只有一个元素，子集为2，那么n=2时，就为2*2，这样推下去，就很容易得到2^n次这个结论。然后你可以画一个2^n行n列的矩阵，按行依次写下0到(2^n)-1的2进制数。最后，根据矩阵中的1去取nums中对应下标的数，每一行的组合就是一个子集，这样就得到了全部的子集。例如：nums=[1,2,3]，则子集数量有8个，按前面所有的方法建立矩阵，为1位上，取下标对应的nums中的元素，为0位上不取，如下：
下为子集号，右为下标 2 1 0
0 0 0 0 []
1 0 0 1 [1]
2 0 1 0 [2]
3 0 1 1 [2,1]
4 1 0 0 [3]
5 1 0 1 [3,1]
6 1 1 0 [3,2]
7 1 1 1 [3,2,1]
根据上面的示例，应该会清楚代码是啥意思。(j » i) & 1这句代码就是判断矩阵中当前i位置上的值是否为1，例如5的2进制数为101，101»2=1，101»1=10，101»0=101，1&1=1，10&1=0，101&1=1。这样就晓得当前行i位置上的数为1还是0了。
总结
递归可能没那么好发现，需要自己多推几步题目的要求，发现有重复、嵌套的步骤时，差不多就可以确定用递归了。然后递归转非递归，就需要通过辅助栈去记录递归中压栈的关键数据。而另外一些非常规的解法，可能就需要更多的细心观察和强大的数学能力了。