全排列

原题链接

使用的方法

回溯算法

解题思路

• 给定一个不含重复数字的数组，我们需要返回该数组所有可能的全排列。全排列是指数组中元素的所有可能的顺序组合。
• 我们可以使用回溯算法来解决这个问题。回溯算法是一种系统地搜索所有可能的解决方案的方法。在这个问题中，我们可以通过交换数组中的元素来生成不同的排列。
• 我们从数组的第一个元素开始，依次交换当前元素与后续元素的位置，然后递归地生成剩余元素的全排列。每次递归完成后，我们需要将交换的元素恢复到原来的位置，以便继续生成其他的排列。
• 递归的终止条件是当我们处理到数组的最后一个元素时，我们将当前的排列添加到结果列表中。通过这种方式，我们可以生成所有可能的全排列，并最终返回结果列表。

代码实现

class Solution {
    List<Integer> nums;
    List<List<Integer>> res;
    public List<List<Integer>> permute(int[] nums) {
        this.res = new ArrayList<>();
        this.nums = new ArrayList<>();
        for(int n : nums){
            this.nums.add(n);
        }
        dfs(0);
        return res;
    }

    void swap(int a,int b){
        int temp = nums.get(a);
        nums.set(a,nums.get(b));
        nums.set(b,temp);
    }

    void dfs(int x){
        if(x == nums.size()-1){
            res.add(new ArrayList<>(nums));
            return;
        }
        for(int i = x;i < nums.size();i++){
            swap(i,x);
            dfs(x+1);
            swap(i,x);
        }
    }
}