深度优先搜索属于图算法的一种，英文缩写为DFS即Depth First Search。
其过程简要来说是对每一个可能的分支路径深入到不能再深入为止，而且每个节点只能访问一次。
1 全排列
给定一个字符数组，对所有元素进行全排列并逐行输出。
DFS函数，详解见注释：
/**
* The dfs function to achieve the full permutation of the letters
* @param letters The given array storing the letters
* @param level The level of the permutation
* @param ans The array storing letters arranged
*/
public static void dfs(char[] letters, int level, char[] ans) {
// 1. The end condition
if (level == letters.length) {
System.out.println(Arrays.toString(ans));
return;
}
// 2. Iterates over the candidate nodes in the given array
for (int i = 0; i < letters.length; i ++) {
char c = letters[i];
if (c != '\0') { // The next letter is not used
ans[level] = c; // Stores it
letters[i] = '\0'; // The letter is used
dfs(letters, level+1, ans); // dfs, the level ++
letters[i] = c; // Recovers the boolean array
}
}
}测试：
char[] letters = new char[] {'A', 'B', 'C'};
dfs(letters, 0, new char[letters.length]);输出：
[A, B, C]
[A, C, B]
[B, A, C]
[B, C, A]
[C, A, B]
[C, B, A]NOTE
对布尔数组的恢复语句写在if语句中，dfs函数调用后。
2 部分排列
部分排列与全排列的区别只有答案数组的长度发生了变化，此外只需修改深搜函数的递归头部分（结束条件）即可。
3 组合
相较于部分排列而言，组合具有无序性，因此为防止元素重复，循环的起始条件也要作为参数存入深搜函数且每次调用都要进行更新。
组合DFS函数：
public static void dfs(char[] letters, int level, char[] ans, int origin) {
if (level == ans.length) {
System.out.println(Arrays.toString(ans));
return;
}
for (int i = origin; i < letters.length; i ++) { // Changes the original parameter
ans[level] = letters[i];
dfs(letters, level+1, ans, i+1); // Updates the 'origin'
}
}测试及输出：
char[] letters = new char[] {'A', 'B', 'C', 'D'};
dfs(letters,0, new char[3], 0);[A, B, C]
[A, B, D]
[A, C, D]
[B, C, D]NOTE
组合不需要判断元素是否使用过，因为在往更深层跳循环的时候起点一直在更新。
例1 选数求和
题目来源：P1036 NOIP2002 普及组 选数 - 洛谷
题目描述
已知 $n$ 个整数 $x_1,x_2,\cdots,x_n$，以及 $1$ 个整数 $k$（$k<n$）。从 $n$ 个整数中任选 $k$ 个整数相加，可分别得到一系列的和。例如当 $n=4$，$k=3$，$4$ 个整数分别为 $3,7,12,19$ 时，可得全部的组合与它们的和为：
$3+7+12=22$
$3+7+19=29$
$7+12+19=38$
$3+12+19=34$
现在，要求你计算出和为素数共有多少种。
例如上例，只有一种的和为素数：$3+7+19=29$。
输入格式
第一行两个空格隔开的整数 $n,k$（$1 \le n \le 20$，$k<n$）。
第二行 $n$ 个整数，分别为 $x_1,x_2,\cdots,x_n$（$1 \le x_i \le 5\times 10^6$）。
输出格式
输出一个整数，表示种类数。
样例 #1
样例输入 #1
4 3
3 7 12 19样例输出 #1
1题解
import java.util.Scanner;
public class Main {
static int count = 0;
public static void main(String[] args) {
Scanner keyboard = new Scanner(System.in);
int n = keyboard.nextInt();
int k = keyboard.nextInt();
int[] nums = new int[n];
for (int i = 0; i < nums.length; i++) {
nums[i] = keyboard.nextInt();
}
keyboard.close();
dfs(nums, 0, k, 0, 0);
System.out.println(count);
}
public static boolean isPrime(int num) {
if (num == 1) {
return false;
}
for(int num1 = 2; num1 <= Math.sqrt(num); num1 ++) {
if (num % num1 == 0) {
return false;
}
}
return true;
}
public static void dfs(int[] nums, int level, int condition, int origin, int sum) {
if (level == condition) {
if (isPrime(sum)) {
count ++;
}
return;
}
for (int i = origin; i < nums.length; i ++) {
dfs(nums, level+1, condition, i+1, sum + nums[i]);
}
}
}
NOTE
在函数调用中进行求和操作