DFS進階1——回溯
先說一下回溯的板子
dfs(){
for(......){標記信息dfs()撤銷標記
}
}
回溯模板——遞歸實現排列型枚舉
題目分析
其實就是對1~n的數字全排列，這里就可以用dfs去做，1~n全排列我其實是確定每一個位置我應該放哪一個數字，那么dfs的時候就是對位置dfs，dfs(1)表示我現在要選擇一個數放在第一個位置，那么可以選擇的范圍是1~n，
for(int i = 1;i <= n;i++)
且這個數之前沒有被選過，那么我們就要用一個數組book[i]標記一下，book[i]=1表示這個數已經被選走了，那么我就不能再選這個數了。
for(int i = 1;i <= n;i++){if(book[i]==1) continue;
}
當我遍歷到dfs(n+1)時說明我前n個位置都安排完了，那么我就要輸出此時的一個排列，我需要知道我此時選出來的數的排列，那么也可以考慮用一個變量保存，這里我使用的是隊列。
if(k==n+1) {ArrayDeque<Integer> queueTemp = new ArrayDeque<Integer>();queueTemp.addAll(queue);while(!queueTemp.isEmpty()) {System.out.print(queueTemp.pollFirst() + " ");}System.out.println();return;}
當我選擇數i作為當前位置的數時，我要標記這個數已經被選擇了并且把它放入隊列，這個位置選好后，我要繼續選擇下一個位置，所以dfs(k+1)
for(int i = 1;i <= n;i++) {if(book[i]==1) continue;book[i]=1;queue.addLast(i);dfs(k+1);}
當我從dfs退出后再次回來，說明我要嘗試選擇其它數了，那么我要把選這個數做的標記都撤銷，包括，book數組對應位置置為0和把這個數從隊列里面拿出來。
for(int i = 1;i <= n;i++) {if(book[i]==1) continue;book[i]=1;queue.addLast(i);dfs(k+1);book[i]=0;queue.pollLast();}
題目代碼
import java.util.ArrayDeque;
import java.util.Scanner;
public class Main{static ArrayDeque<Integer> queue = new ArrayDeque<Integer>();static int book[];static int n;
public static void main(String[] args) {Scanner scanner = new Scanner(System.in);n = scanner.nextInt();book = new int[n+1];dfs(1);
}private static void dfs(int k) {// TODO Auto-generated method stubif(k==n+1) {ArrayDeque<Integer> queueTemp = new ArrayDeque<Integer>();queueTemp.addAll(queue);while(!queueTemp.isEmpty()) {System.out.print(queueTemp.pollFirst() + " ");}System.out.println();return;}for(int i = 1;i <= n;i++) {if(book[i]==1) continue;book[i]=1;queue.addLast(i);dfs(k+1);book[i]=0;queue.pollLast();}
}
}
