<font size="6px">
一、部分和问题</font>
题目描述：给定整数序列a1，a2，.....，an，判断是否可以从中选出若干数，使他们的和恰好为k。
1<=n<=20
-10^8 <= ai <= 10^8
-10^8 <= k <= 10^8
样例：
输入
n=4
a={1,2,4,7}
k=13
输出
Yes （13=2+4+7）
思路分析：这道题目首先按照题目进行输入。之后调用dfs1（）方法，将数组，k，以及数组的首位置传过去（作为0状态）。然后开始遍历位置，每一个位置都面临两种选择，第一种选择是取这个位置的值，第二种选择是不取这个位置的值。第一种选择不取这个位置的值就去查看下一个位置的值，就对应代码dfs1(arr,k,current+1);，只有状态加一，其余不变。第二种选择取这个位置的值，就将该位置的值存入list中，并获得index。然后调用代码dfs1(arr,k-arr[current],current+1);，可见k的值减去该位置的值，同样状态+1。这题有一个必要的点是要记得回溯，如果这条路走不通，要回溯到原来的状态，就是将该位置的值在list中删除，对应代码list.remove(index); 。最后一步就是确定出口，当k等于0时就输出结果。当k<0或者current==arr.length时说明这条路走不通，返回继续寻找其他路径。
static int kk;
static ArrayList<Integer> list=new ArrayList<>(); //存放计算过程
//部分和问题
public static void main(String[] args) {
Scanner reader=new Scanner(System.in);
int n=reader.nextInt();
int[] arr=new int[n];
for(int i=0;i<arr.length;i++) { //按题目输入
arr[i]=reader.nextInt();
}
kk=reader.nextInt();
dfs1(arr,kk,0); //调用深度优先搜索
}
public static void dfs1(int[] arr,int k,int current) {
if(k==0) { //出口
System.out.print("Yes (");
System.out.print(kk+"=");
for(int j=0;j<list.size();j++) {
if(j==list.size()-1) {
System.out.print(list.get(j));
}else {
System.out.print(list.get(j)+"+");
}
}
System.out.println(")");
System.exit(0);
}
if(current==arr.length||k<0) { //没有找到答案
return;
}
dfs1(arr,k,current+1); //第一种情况，不取，状态+1
list.add(arr[current]); //将该状态的数字存入list中
int index=list.size()-1; //记录位置，方便回溯
dfs1(arr,k-arr[current],current+1); //第二种情况，取，状态+1
list.remove(index); //回溯
}
<font size="6px">
二、水洼数目问题</font>
题目描述：有一个大小为NM的园子，雨后积起了水，八连通的积水被认为是连接在一起的。请求出园子里总共有多少水洼？（八连通值得是下图中相对W的*的部分）
***
*W*
***
限制条件：
N,M<=100
样例：
输入
N=10,M=12
园子如下图：
输出
3*
思路分析：这道题目首先按照题目进行输入,将园子存入字符数组中。之后循环遍历园子，查看那个点位存在水洼，就调用dfs2（）方法去清除与该点连通的水洼。方法中，以（i,j）为起点，有8个位置可以行走，但是不能重复上一层，故要先清除（i，j）位上的水洼。然后8个位置分为就是k=-1，0，1，j=-1，0，1.然后要排除k=0，j=0的情况，并且注意越界。如果（i+k，j+q）存在连通水洼，则调用方法清除水洼。最后输出结果
// 水洼数目问题
static char[][] arr; //字符数组，存放园子
static int N, M;
static int count=0; //记录水洼数目
public static void main(String[] args) {
Scanner reader = new Scanner(System.in);
N = reader.nextInt();
M = reader.nextInt();
arr = new char[N][];
for (int i = 0; i < N; i++) {
arr[i] = reader.next().toCharArray(); //初始化园子
}
for (int i = 0; i < N; i++) { //循环遍历园子的每一个位置
for (int j = 0; j < M; j++) {
if (arr[i][j] == 'W') { //如果是W
dfs2(i, j); //调用函数，清除水洼
count++; //水洼数+1
}
}
}
System.out.println(count);
}
private static void dfs2(int i, int j) {
arr[i][j] = '.'; //清除该水洼
//遍历查询与该点连通的水洼
for (int k = -1; k < 2; k++) { //-1，0，1
for (int q = -1; q < 2; q++) { //-1，0，1
if (k == q && q == 0) {
continue;
}
if (i + k >= 0 && j + q >= 0 && i + k <= N - 1 && j + q <= M - 1) { //限定范围
if (arr[i + k][j + q] == 'W') { //如果存在连通的水洼
dfs2(i + k, j + q); //递归调用，清除水洼
}
}
}
}
}
<font size="6px">
三、n皇后问题</font>
题目描述：请设计一种算法，解决著名的n皇后问题。这里的n皇后问题指在一个nn的棋盘上放置n个棋子，使得每行每列和每条对角线上都只有一个棋子，求其摆放的方法数。
给定一个int n，请返回方法数，保证n小于等于15*
思路分析：这道题目首先按照题目进行输入,创建一个整形数组，用来放每一行皇后的位置，调用dfs3（）方法，从第0行开始遍历。因为有n行，要放n个皇后所以肯定是每行一个皇后，故for (int i = 0; i < n; i++)用来遍历每一行中的每一个位置，for (int j = 0; j < row; j++)用来遍历数组中之前每一行的皇后的位置。然后对（row，i）位置判断是否能放皇后，如果不能放，就置judge为false。判断的条件主要有三个。1、同一列上不能有多个皇后。2、正对角线上不能有多个皇后（正对角线上x和y之和相等）3、反对角线上不能有多个皇后（反对角线上y-x的差相等）。如果judge为true，就将该位置存入整形数组，递归调用下一行。如果方法无法进行下去，就要回溯。最后要设置出口。
//n皇后问题
static int[] arr; // 整形数组，用来存放每一行皇后的位置
static int count; // 记录有多少种解法
public static void main(String[] args) {
Scanner reader = new Scanner(System.in);
int n = reader.nextInt();
arr = new int[n];
dfs3(n, 0); // 调用深度优先搜索
System.out.println(count); // 打印结果
}
private static void dfs3(int n, int row) {
if (row == n) { //出口
count++;
return;
}
for (int i = 0; i < n; i++) { //遍历每一行中的每个位置
boolean judge = true; //初始化
for (int j = 0; j < row; j++) { //遍历row行以前的皇后的
if (arr[j] == i || row + i == j + arr[j] || i - row == arr[j] - j) { //判定该位置是否能放皇后
judge = false; //不能放皇后
}
}
if (judge) { //如果judge为true
arr[row] = i; //将row行i号位放置皇后
dfs3(n, row + 1); //递归调用下一行的皇后
arr[row] = 0; //方法不成功，回溯
}
}
}
<font size="6px">
四、素数环问题</font>
题目描述：对于正整数n，对1~n进行排列，使得相邻两个数之和均为素数，输出时从整数1开始，逆时针排列。同一个环应恰好输出一次
n<=16
如输入：6
输出：
1 4 3 2 5 6
1 6 5 2 3 4
思路分析：这道题目首先按照题目进行输入,创建一个整形数组，用来存放素数环每一个位置的数字。首先将1存入数组，然后调用dfs4（）方法。for (int i = 1; i < n + 1; i++)尝试将每一个数字填入到数组中，然后for (int j = 0; j < count; j++)循环遍历是否数组中已经存在这个数。如果不是，接着判断相邻两个数之和是否为素数，如果是素数，递归调用下一个数，将本次循环的数传给下一次循环，以便判断相邻的数。最后设置出口，要记得判断最后一个数字和第一个数字能否形成素数环，如果可以，就输出结果。
// 素数环问题
static int[] arr; //整形数组，存放每一个位置的值
static int count; //数组中的个数
public static void main(String[] args) {
Scanner reader = new Scanner(System.in);
int n = reader.nextInt();
arr = new int[n];
arr[0] = 1; //将1存入数组
count++;
dfs4(n, 1); //调用深度优先搜索
}
private static void dfs4(int n, int k) {
if (count == n) { //出口
if (judgePrimeNumber(arr[0] + arr[n-1])) { //判断最后一个数字和第一个数字之和是不是素数
for (int i = 0; i < n ; i++) {
System.out.print(arr[i]); //输出
}
System.out.println();
}
return;
}
for (int i = 1; i < n + 1; i++) { //尝试用每一个数加入到数组中
boolean judge = true;
for (int j = 0; j < count; j++) { //判断这个数是否已经被选过
if (i == arr[j]) {
judge = false;
}
}
if (judge == true) {
if (judgePrimeNumber(k+i)) { //判断相邻的数之和是否为素数
arr[count] = i; //添加到数组中
count++;
dfs4(n, i); //递归调用下一个数
count--;
arr[count] = i; //回溯
}
}
}
}
public static boolean judgePrimeNumber(int k) { //判断是否为素数
int q;
for (q = 2; q < k; q++) {
if (k % q == 0) {
return false;
}
}
return true;
}
<font size="6px">
五、困难的串问题</font>
题目描述：如果一个字符串包含两个相邻的重复子串，则称它为容易的串，其他的串称为困难的串。
如：BB,ADCDACABCAB,ABCDABCD都是容易的串，D,DC,ADBAB,CBABCBA都是困难的。
输入正整数n，L，输出由前L个字符组成的，字典序第n小的困难的串。
例如，当L=3时，前7个困难的串分别为：
A,AB,ABA,ABAC,ABACA,ABACAB,ABACABA
n指定为4的话，输出ABAC
思路分析：这道题目首先按照题目进行输入，创建一个count用来存放第几个。调用dfs5（）方法。按照字典序遍历，然后调用isHard（）方法判断是否把i加进去也构成苦难的串，如果成立，就将i添加到prefix的末尾，count++，继续递归调用，直到最后输出。判断苦难的串的方法，是从后往前遍历。
//困难的串
static int L,n;
static int count=0; //用来记录第几个
public static void main(String[] args) {
Scanner reader=new Scanner(System.in);
n=reader.nextInt();
L=reader.nextInt();
dfs5(""); //调用深度优先搜索
}
private static void dfs5(String prefix) {
for(int i='A';i<='A'+L+1;i++) { //按照字典序遍历
if(isHard(prefix,i)) { //判断将i加进字符串中，是否还构成困难的串
String x=prefix+i; //将i加入字符串中
count++;
if(count==n) { //出口
System.out.println(x);
System.exit(0);
}
dfs5(x); //递归调用，继续寻找
}
}
}
private static boolean isHard(String prefix, int i) { //判断将i加进字符串中，是否还构成困难的串
int cnt=0;
for(int j=prefix.length()-1;j>=0;j-=2) { //从末至尾判断是否是苦难的串
String x1=prefix.substring(j,j+cnt+1);
String x2=prefix.substring(j+cnt+1)+i;
if(x1.equals(x2)) { //是否相同，则为容易的串
return false;
}
cnt++;
}
return true;
}
