給定一個不含重復數字的數組 nums ，返回其 所有可能的全排列 。你可以 按任意順序 返回答案。

示例 1：
輸入：nums = [1,2,3]
輸出：[[1,2,3],[1,3,2],[2,1,3],[2,3,1],[3,1,2],[3,2,1]]

示例 2：
輸入：nums = [0,1]
輸出：[[0,1],[1,0]]

示例 3：
輸入：nums = [1]
輸出：[[1]]

提示：
1 <= nums.length <= 6
-10 <= nums[i] <= 10
nums 中的所有整數 互不相同

---

知識點：
回溯、數組

---

解：
核心思路：
用數組記錄節點是否被訪問過
用集合記錄已訪問的節點
每次遍歷時，選擇一個未被訪問的節點進行訪問
恢復現場的目的：假設當前遍歷節點3，但結果不滿足，需要回溯到上一個節點，若不恢復現場，節點3將不能再訪問了

時間復雜度：$O(n?n!)$。從根節點到葉子節點的路徑長度之和，共有n!個節點
空間復雜度：$O(n)$。

class Solution {public List<List<Integer>> permute(int[] nums) {//獲取數組大小int len = nums.length;//存儲結果List<List<Integer>> res = new ArrayList<>();//路徑List<Integer> path = Arrays.asList(new Integer[len]); // 所有排列的長度都是len//是否遍歷過boolean[] isUsed = new boolean[len];//執行DFSdfs(0, nums, len, res, path, isUsed);return res;}private void dfs(int depth, int[] nums, int len, List<List<Integer>> res, List<Integer> path, boolean[] isUsed) {//葉子節點if (depth == len) {res.add(new ArrayList<>(path));return;}//遍歷所有節點for (int i = 0; i < len; i++) {//未訪問過if (!isUsed[i]) {//從未選過的數字中選一個path.set(depth, nums[i]);//標記為已訪問isUsed[i] = true;//遞歸下一個節點dfs(depth + 1, nums, len, res, path, isUsed);//恢復現場isUsed[i] = false;//路徑無需恢復現場，因為排列長度固定，直接覆蓋即可}}}
}

---

參考：
1、靈神題解