2020-09-16 更新
今天发现“常用算法与数据结构模板”这个主题的内容写得实在是太多了，以至于放在一篇博文里面 显得不太合适。所以今天把这个主题分拆成一系列的文章（话说，这其实应该是我写的第一个系列）。
DFS
模板如下：
void dfs(int 当前状态)
{
if(当前状态为边界状态)
{
记录或输出
return;
}
for(每一个子状态) //横向遍历解答树所有子节点
{
修改了全局变量
if(子状态满足约束条件)
{
dfs(子状态)
}
恢复全局变量//回溯部分
}
}
实例：
# 题目：输出一个数组中所有元素的全排列
def full_permutation(arr):
visited = [1] * len(arr)
temp = arr[:] # 浅拷贝
result = []
def dfs(position):
if position == len(arr):
result.append(temp[:]) # 浅拷贝，否则result中所有行都一样
return
for index in range(len(arr)): # range all possible paths downside
if visited[index]:
temp[position] = arr[index]
visited[index] = 0
dfs(position+1)
visited[index] = 1
dfs(0)
return result
print(full_permutation([1,2,3]))
# [[1, 2, 3], [1, 3, 2], [2, 1, 3], [2, 3, 1], [3, 2, 1], [3, 1, 2]]
// 题目：给定一个整型数组, 你的任务是找到所有该数组的递增子序列，递增子序列的长度至少是2。
// 示例:
// 输入: [4, 6, 7, 7]
// 输出: [[4, 6], [4, 7], [4, 6, 7], [4, 6, 7, 7], [6, 7], [6, 7, 7], [7,7], [4,7,7]]
// 说明:
// 给定数组的长度不会超过15。
// 数组中的整数范围是 [-100,100]。
// 给定数组中可能包含重复数字，相等的数字应该被视为递增的一种情况。
import java.util.ArrayList;
import java.util.List;
class Solution { // 递归枚举
private List<List<Integer>> res = new ArrayList<>();
private int[] nums;
public List<List<Integer>> findSubsequences(int[] nums) {
this.nums = nums;
backtrace(new ArrayList<Integer>(), 0, Integer.MIN_VALUE);
return res;
}
private void backtrace(List<Integer> path, int cur, int last) {
if (cur >= nums.length) {
if (path.size() >= 2) {
res.add(new ArrayList<>(path)); // note to copy `path`
}
return;
}
if (last != nums[cur]) { // last 用于防止重复枚举
// 两个相同元素有四种情况：
// 前者被选择，后者被选择
// 前者被选择，后者不被选择
// 前者不被选择，后者被选择
// 前者不被选择，后者不被选择
// 第二种情况和第三种情况是重复的，我们令“前者被选择时后者必被选择”，舍弃了第二种
backtrace(path, cur + 1, last);
}
if (nums[cur] >= last) {
path.add(nums[cur]);
backtrace(path, cur + 1, nums[cur]);
path.remove(path.size() - 1); // `path` is reused throughout the whole DFS
}
}
}
最后附上 GitHub：https://github.com/gonearewe
