大厂面试编程算法必考总结----循环、递归、回溯--例求子集-轻识

本文的关键在于解决大家一看就会，一写就废的问题。

接下来以一道编程题来举例子：

阿里面试编程题：

求1-N 元素构成的子集！

在这里我总结了四种方法：

循环
递归
回溯
位运算

1、循环

解题思路如下：

def all_set(arr):
result_all = [[]]
for i in arr:
result_all.extend([re+[i] for re in result_all])
return result_all

循环大家都知道什么意思，不用过多解释。

2、递归

什么叫递归？

递归：无限调用自身这个函数，每次调用总会改动一个关键变量，直到这个关键变量达到边界的时候，不再调用。

进一步剖析「递归」，先有「递」再有「归」，「递」的意思是将问题拆解成子问题来解决，子问题再拆解成子子问题，...，直到被拆解的子问题无需再拆分成更细的子问题（即可以求解），「归」是说最小的子问题解决了，那么它的上一层子问题也就解决了，上一层的子问题解决了，上上层子问题自然也就解决了,....,直到最开始的问题解决,文字说可能有点抽象，那我们就以阶层 f(6) 为例来看下它的「递」和「归」。

比如说我要你先求一个N!的结果

你说我会用循环啊（没错，但是现在是学递归）

1 int factorial(int x,int ans)
2 {
3 if(x==1)
4 return ans;
5 factorial(x-1,ans*x);
6 }

递归解题思路的思想是采用数学归纳法：

首先解决基础情景 f(1)
然后假定已经解决了问题 f（n-1）
接下来解决问题N

#解题代码如下：
result_all = [[]]
n=len(arr)
def recursion_set(arr,n):
if n==1:
result_all.append([1])
return result_all
else:
result_all.extend([a + [arr[n-1]] for a in recursion_set(arr, n-1)])
return result_all

上述问题考虑递归解决的话，可以这样考虑，[1,2,3] 的子集可以由 [1,2] 追加得出，[1,2] 的子集可以由 [1] 追加得出，先得出为[1]的时候的结果。自然而然就写出代码如上。

3、回溯算法

回溯法中，首先需要明确下面三个概念：

约束函数：约束函数是根据题意定出的。通过描述合法解的一般特征用于去除不合法的解，从而避免继续搜索出这个不合法解的剩余部分。因此，约束函数是对于任何状态空间树上的节点都有效、等价的。
状态空间树：刚刚已经提到，状态空间树是一个对所有解的图形描述。树上的每个子节点的解都只有一个部分与父节点不同。
扩展节点、活结点、死结点：所谓扩展节点，就是当前正在求出它的子节点的节点，在DFS中，只允许有一个扩展节点。活结点就是通过与约束函数的对照，节点本身和其父节点均满足约束函数要求的节点；死结点反之。由此很容易知道死结点是不必求出其子节点的（没有意义）。

回溯算法框架：

result = []
def backtrack(路径, 选择列表):
if 满足结束条件:
result.add(路径)
return

for 选择 in 选择列表:
做选择
backtrack(路径, 选择列表)
撤销选择

其核心就是 for 循环里面的递归，在递归调用之前「做选择」，在递归调用之后「撤销选择」，特别简单

全排列问题：排列组合的数学题，我们也知道 n 个不重复的数，全排列共有 n! 个

#回溯法思想:以[1,2,3]为例，从子集的元素个数角度去拆解：空集、只含一个元素、只含两个元素、只含三个元素
nums = [1,2,3]
def subset(nums):
def backtrack(first=0, curr=[]):
## 递归函数的出口
if len(curr) == k:
res.append(curr[:])
## 设计递归函数结构
for i in range(first, len(nums)):
curr.append(nums[i])
backtrack(i + 1, curr)
curr.pop()
res = []
for k in range(len(nums) + 1):
# 计算每一类的子集
backtrack()
return res

4 、位运算

def PowerSetsBinary(items):
N = len(items)
# generate all combination of N items
# enumerate the 2**N possible combinations
for i in range(2 ** N):
combo = []
for j in range(N): # jth bit of Integer i
if (i >> j) % 2 == 1:
combo.append(items[j])
yield combo