<font size="6px">
一、部分和問題</font>
題目描述：給定整數(shù)序列a1葬项，a2泞当，.....，an民珍，判斷是否可以從中選出若干數(shù)襟士，使他們的和恰好為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）
思路分析：這道題目首先按照題目進(jìn)行輸入。之后調(diào)用dfs1（）方法陋桂，將數(shù)組箩兽，k，以及數(shù)組的首位置傳過去（作為0狀態(tài)）章喉。然后開始遍歷位置，每一個位置都面臨兩種選擇身坐，第一種選擇是取這個位置的值秸脱，第二種選擇是不取這個位置的值。第一種選擇不取這個位置的值就去查看下一個位置的值部蛇，就對應(yīng)代碼dfs1(arr,k,current+1);摊唇，只有狀態(tài)加一，其余不變涯鲁。第二種選擇取這個位置的值巷查，就將該位置的值存入list中，并獲得index抹腿。然后調(diào)用代碼dfs1(arr,k-arr[current],current+1);岛请，可見k的值減去該位置的值，同樣狀態(tài)+1警绩。這題有一個必要的點(diǎn)是要記得回溯崇败，如果這條路走不通，要回溯到原來的狀態(tài)肩祥，就是將該位置的值在list中刪除后室，對應(yīng)代碼list.remove(index); 。最后一步就是確定出口混狠，當(dāng)k等于0時就輸出結(jié)果岸霹。當(dāng)k<0或者current==arr.length時說明這條路走不通，返回繼續(xù)尋找其他路徑将饺。
static int kk;
static ArrayList<Integer> list=new ArrayList<>(); //存放計(jì)算過程
//部分和問題
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); //調(diào)用深度優(yōu)先搜索
}
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); //第一種情況贡避，不取，狀態(tài)+1
list.add(arr[current]); //將該狀態(tài)的數(shù)字存入list中
int index=list.size()-1; //記錄位置予弧，方便回溯
dfs1(arr,k-arr[current],current+1); //第二種情況贸桶，取，狀態(tài)+1
list.remove(index); //回溯
}
<font size="6px">
二桌肴、水洼數(shù)目問題</font>
題目描述：有一個大小為NM的園子皇筛，雨后積起了水，八連通的積水被認(rèn)為是連接在一起的坠七。請求出園子里總共有多少水洼水醋？（八連通值得是下圖中相對W的*的部分）
???????***
???????*W*
???????***
限制條件：
???????N,M<=100
樣例：
輸入
???????N=10,M=12
園子如下圖：
輸出
???????3*
思路分析：這道題目首先按照題目進(jìn)行輸入,將園子存入字符數(shù)組中旗笔。之后循環(huán)遍歷園子，查看那個點(diǎn)位存在水洼拄踪，就調(diào)用dfs2（）方法去清除與該點(diǎn)連通的水洼蝇恶。方法中，以（i,j）為起點(diǎn)惶桐，有8個位置可以行走撮弧，但是不能重復(fù)上一層，故要先清除（i姚糊，j）位上的水洼贿衍。然后8個位置分為就是k=-1，0救恨，1贸辈，j=-1，0肠槽，1.然后要排除k=0擎淤，j=0的情況，并且注意越界秸仙。如果（i+k嘴拢，j+q）存在連通水洼，則調(diào)用方法清除水洼寂纪。最后輸出結(jié)果
// 水洼數(shù)目問題
static char[][] arr; //字符數(shù)組炊汤，存放園子
static int N, M;
static int count=0; //記錄水洼數(shù)目
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++) { //循環(huán)遍歷園子的每一個位置
for (int j = 0; j < M; j++) {
if (arr[i][j] == 'W') { //如果是W
dfs2(i, j); //調(diào)用函數(shù)，清除水洼
count++; //水洼數(shù)+1
}
}
}
System.out.println(count);
}
private static void dfs2(int i, int j) {
arr[i][j] = '.'; //清除該水洼
//遍歷查詢與該點(diǎn)連通的水洼
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); //遞歸調(diào)用迈倍，清除水洼
}
}
}
}
}
<font size="6px">
三、n皇后問題</font>
題目描述：請?jiān)O(shè)計(jì)一種算法捣域，解決著名的n皇后問題啼染。這里的n皇后問題指在一個nn的棋盤上放置n個棋子，使得每行每列和每條對角線上都只有一個棋子焕梅，求其擺放的方法數(shù)迹鹅。
給定一個int n，請返回方法數(shù)贞言，保證n小于等于15*
思路分析：這道題目首先按照題目進(jìn)行輸入,創(chuàng)建一個整形數(shù)組斜棚，用來放每一行皇后的位置，調(diào)用dfs3（）方法，從第0行開始遍歷弟蚀。因?yàn)橛衝行蚤霞，要放n個皇后所以肯定是每行一個皇后，故for (int i = 0; i < n; i++)用來遍歷每一行中的每一個位置义钉，for (int j = 0; j < row; j++)用來遍歷數(shù)組中之前每一行的皇后的位置昧绣。然后對（row，i）位置判斷是否能放皇后捶闸，如果不能放夜畴，就置judge為false。判斷的條件主要有三個删壮。1贪绘、同一列上不能有多個皇后。2醉锅、正對角線上不能有多個皇后（正對角線上x和y之和相等）3、反對角線上不能有多個皇后（反對角線上y-x的差相等）发绢。如果judge為true硬耍，就將該位置存入整形數(shù)組，遞歸調(diào)用下一行边酒。如果方法無法進(jìn)行下去经柴，就要回溯。最后要設(shè)置出口墩朦。
//n皇后問題
static int[] arr; // 整形數(shù)組坯认，用來存放每一行皇后的位置
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); // 調(diào)用深度優(yōu)先搜索
System.out.println(count); // 打印結(jié)果
}
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); //遞歸調(diào)用下一行的皇后
arr[row] = 0; //方法不成功，回溯
}
}
}
<font size="6px">
四氓涣、素?cái)?shù)環(huán)問題</font>
題目描述：對于正整數(shù)n牛哺，對1~n進(jìn)行排列，使得相鄰兩個數(shù)之和均為素?cái)?shù)劳吠，輸出時從整數(shù)1開始引润，逆時針排列。同一個環(huán)應(yīng)恰好輸出一次
n<=16
如輸入：6
輸出：
1 4 3 2 5 6
1 6 5 2 3 4
思路分析：這道題目首先按照題目進(jìn)行輸入,創(chuàng)建一個整形數(shù)組痒玩，用來存放素?cái)?shù)環(huán)每一個位置的數(shù)字淳附。首先將1存入數(shù)組，然后調(diào)用dfs4（）方法蠢古。for (int i = 1; i < n + 1; i++)嘗試將每一個數(shù)字填入到數(shù)組中奴曙，然后for (int j = 0; j < count; j++)循環(huán)遍歷是否數(shù)組中已經(jīng)存在這個數(shù)。如果不是草讶，接著判斷相鄰兩個數(shù)之和是否為素?cái)?shù)洽糟，如果是素?cái)?shù)，遞歸調(diào)用下一個數(shù)，將本次循環(huán)的數(shù)傳給下一次循環(huán)脊框，以便判斷相鄰的數(shù)颁督。最后設(shè)置出口，要記得判斷最后一個數(shù)字和第一個數(shù)字能否形成素?cái)?shù)環(huán)浇雹，如果可以沉御，就輸出結(jié)果。
// 素?cái)?shù)環(huán)問題
static int[] arr; //整形數(shù)組昭灵，存放每一個位置的值
static int count; //數(shù)組中的個數(shù)
public static void main(String[] args) {
Scanner reader = new Scanner(System.in);
int n = reader.nextInt();
arr = new int[n];
arr[0] = 1; //將1存入數(shù)組
count++;
dfs4(n, 1); //調(diào)用深度優(yōu)先搜索
}
private static void dfs4(int n, int k) {
if (count == n) { //出口
if (judgePrimeNumber(arr[0] + arr[n-1])) { //判斷最后一個數(shù)字和第一個數(shù)字之和是不是素?cái)?shù)
for (int i = 0; i < n ; i++) {
System.out.print(arr[i]); //輸出
}
System.out.println();
}
return;
}
for (int i = 1; i < n + 1; i++) { //嘗試用每一個數(shù)加入到數(shù)組中
boolean judge = true;
for (int j = 0; j < count; j++) { //判斷這個數(shù)是否已經(jīng)被選過
if (i == arr[j]) {
judge = false;
}
}
if (judge == true) {
if (judgePrimeNumber(k+i)) { //判斷相鄰的數(shù)之和是否為素?cái)?shù)
arr[count] = i; //添加到數(shù)組中
count++;
dfs4(n, i); //遞歸調(diào)用下一個數(shù)
count--;
arr[count] = i; //回溯
}
}
}
}
public static boolean judgePrimeNumber(int k) { //判斷是否為素?cái)?shù)
int q;
for (q = 2; q < k; q++) {
if (k % q == 0) {
return false;
}
}
return true;
}
<font size="6px">
五吠裆、困難的串問題</font>
題目描述：如果一個字符串包含兩個相鄰的重復(fù)子串，則稱它為容易的串烂完，其他的串稱為困難的串试疙。
如：BB,ADCDACABCAB,ABCDABCD都是容易的串，D,DC,ADBAB,CBABCBA都是困難的抠蚣。
輸入正整數(shù)n祝旷，L，輸出由前L個字符組成的嘶窄，字典序第n小的困難的串怀跛。
例如，當(dāng)L=3時柄冲，前7個困難的串分別為：
A,AB,ABA,ABAC,ABACA,ABACAB,ABACABA
n指定為4的話吻谋，輸出ABAC
思路分析：這道題目首先按照題目進(jìn)行輸入，創(chuàng)建一個count用來存放第幾個现横。調(diào)用dfs5（）方法漓拾。按照字典序遍歷，然后調(diào)用isHard（）方法判斷是否把i加進(jìn)去也構(gòu)成苦難的串戒祠，如果成立骇两，就將i添加到prefix的末尾，count++姜盈，繼續(xù)遞歸調(diào)用脯颜，直到最后輸出。判斷苦難的串的方法贩据，是從后往前遍歷栋操。
//困難的串
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(""); //調(diào)用深度優(yōu)先搜索
}
private static void dfs5(String prefix) {
for(int i='A';i<='A'+L+1;i++) { //按照字典序遍歷
if(isHard(prefix,i)) { //判斷將i加進(jìn)字符串中，是否還構(gòu)成困難的串
String x=prefix+i; //將i加入字符串中
count++;
if(count==n) { //出口
System.out.println(x);
System.exit(0);
}
dfs5(x); //遞歸調(diào)用饱亮，繼續(xù)尋找
}
}
}
private static boolean isHard(String prefix, int i) { //判斷將i加進(jìn)字符串中矾芙，是否還構(gòu)成困難的串
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;
}
