框架

返回值要搞清楚,当索引变为负值返回,当达到目标时也要记得返回.

1
2
3
4
5
6
7
8
9
10
result = []
def backrack(路径,选择列表):
	if 满足结束条件:
		result.add(路径)
		return
    #少的话可以直接穷举
	for 选择 in 选择列表
		做选择
		backtrace(路径,选择列表)
		撤销选择

和动态规划的关系

把上边的这部分展开一下

1
2
3
4
5
6
def backrack(游标,一路选择后的结果):
...
for 选择 in 选择列表
	做选择
	backtrace(游标,一路选择后的结果)
	撤销选择	
1
2
3
4
def backtrack(int i,int trace):
	backtrace(i + 1,trace + nums[i]);
	backtrace(i + 1,trace - nums[i]);
	...

当nums[i] = 0时有重复子问题,发现一个必然有很多个因此可以使用备忘录优化