大厂面试编程算法必考总结----循环、递归、回溯--例求子集
共 2374字，需浏览 5分钟
·
2021-02-05 12:45
本文的关键在于解决大家一看就会，一写就废的问题。
接下来以一道编程题来举例子：
阿里面试编程题：
求1-N 元素构成的子集！
在这里我总结了四种方法：
循环
递归
回溯
位运算
1、循环
解题思路如下：
result_all = [[]]
for i in arr:
result_all.extend([re+[i] for re in result_all])
return result_all
循环大家都知道什么意思，不用过多解释。
2、递归
什么叫递归？
递归：无限调用自身这个函数，每次调用总会改动一个关键变量，直到这个关键变量达到边界的时候，不再调用。
进一步剖析「递归」，先有「递」再有「归」，「递」的意思是将问题拆解成子问题来解决， 子问题再拆解成子子问题，...，直到被拆解的子问题无需再拆分成更细的子问题（即可以求解），「归」是说最小的子问题解决了，那么它的上一层子问题也就解决了，上一层的子问题解决了，上上层子问题自然也就解决了,....,直到最开始的问题解决,文字说可能有点抽象，那我们就以阶层 f(6) 为例来看下它的「递」和「归」。
比如说我要你先求一个N!的结果
你说我会用循环啊（没错，但是现在是学递归）
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中，只允许有一个扩展节点。活结点就是通过与约束函数的对照，节点本身和其父节点均满足约束函数要求的节点；死结点反之。由此很容易知道死结点是不必求出其子节点的（没有意义）。
回溯算法框架：
def backtrack(路径, 选择列表):
if 满足结束条件:
result.add(路径)
return
for 选择 in 选择列表:
做选择
backtrack(路径, 选择列表)
撤销选择
其核心就是 for 循环里面的递归，在递归调用之前「做选择」，在递归调用之后「撤销选择」，特别简单
全排列问题：排列组合的数学题，我们也知道 n 个不重复的数，全排列共有 n! 个
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 、位运算
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