回溯經典例題。

題目

通過回溯生成所有可能的排列。每次遞歸時，選擇一個數字，直到選滿所有數字，然后記錄當前排列，回到上層時移除最后選的數字并繼續選擇其他未選的數字。每次遞歸時，在?path?中添加一個新的數字，直到?path?的長度等于數組?nums?的長度，此時可以將?path?添加到結果集中。當遞歸深入到某一層時，我們在返回上層前移除?path?中最后添加的數字，恢復現場，嘗試其他未選的數字。用循環遍歷，然后每次把已加過的數做剔除去選。

記住，dfs遞歸時會逐層進入，即進入后遇到dfs便會進入下一個dfs，逐漸挖到最深層，然后在出口處加入結果集。接著進行回溯，回溯到上一步的dfs后接著執行當前方法的下面的語句，直到當前方法執行完后再次進行回溯，因此回溯的過程中實際上也是進入循環了，這樣也便于選目標元素了。然后遞歸一定要記得加入的是path副本，回溯時要做好恢復。

class Solution {public List<List<Integer>> permute(int[] nums) {LinkedList<List<Integer>> res = new LinkedList<>();            //排列組合結果LinkedList<Integer> path = new LinkedList<>();                     //單個排列dfs(res,nums,path);return res;}public void dfs(List<List<Integer>> res, int[] nums, LinkedList<Integer> path){if(path.size() == nums.length){res.add( new ArrayList<Integer>(path) );     //對于每次添加的單個排列，應該都是不同的引用對象}for(int i=0; i<nums.length; i++){if(path.contains(nums[i]))  {continue;}              //當前層中，已添加的數不再考慮  path.add(nums[i]);                                   //未添加的數則存放dfs(res, nums, path);               //進入下一層（遞歸）path.removeLast();                                  //從深層節點向淺層節點回溯}}
}