46. 全排列（回溯）

同样是回溯算法，相比于前两道题
77. 组合（回溯）
17. 电话号码的字母组合（回溯）
这道题中，对于回溯遍历的内容可以使用一个boolean数组来进行标记判断

class Solution {
   
    public List<List<Integer>> permute(int[] nums) {
   
        List<List<Integer>> ans = new ArrayList<>();
        int n = nums.length;
        boolean[] visited = new boolean[n]; 
        dfs(nums, n, visited, ans, new ArrayList<>());
        return ans;
    }
    public void dfs(int[] nums, int n, boolean[] visited, List<List<Integer>> ans, List<Integer> list) {
   
        if (list.size() == n) ans.add(new ArrayList<>(list));
        else {
   
            for (int i = 0; i < n; ++i) {
   
                if (!visited[i]) {
   
                    int cur = nums[i];
                    list.add(cur);
                    visited[i] = true;
                    dfs(nums, n, visited, ans, list);
                    visited[i] = false;
                    list.remove(list.size() - 1);
                } 
            }
        }
    }
}

特别注意：

1. if条件判断的位置

   for (int i = 0; i < n; ++i) {
        
   	if (!visited[i]) {
        
   

   不要写成

   for (int i = 0; i < n && !visited[i]; ++i) {
        
   

   会出错，但不明白为什么。

2. 深度优先搜索时，回溯重置操作中去除的元素应该是list列表的最后一个元素，而不是n-1

   list.remove(list.size() - 1);
   

   而不是

   list.remove(n - 1);