55.全排列

LCR 083. 全排列

 给定一个不含重复数字的整数数组 nums ，返回其 所有可能的全排列 。可以 按任意顺序 返回答案。

示例 1：

输入：nums = [1,2,3]
输出：[[1,2,3],[1,3,2],[2,1,3],[2,3,1],[3,1,2],[3,2,1]]

来源：力扣官方题解

将题目给定的 n 个数的数组 nums 划分成左右两个部分，左边的表示已经填过的数，右边表示待填的数，我们在回溯的时候只要动态维护这个数组即可。

具体来说，假设我们已经填到第 first 个位置，那么 nums 数组中 [0,first−1] 是已填过的数的集合，[first,n−1] 是待填的数的集合。我们肯定是尝试用 [first,n−1] 里的数去填第 first 个数，假设待填的数的下标为 i，那么填完以后我们将第 i 个数和第 first 个数交换，即能使得在填第 first+1 个数的时候 nums 数组的 [0,first] 部分为已填过的数，[first+1,n−1] 为待填的数，回溯的时候交换回来即能完成撤销操作。

 

总结【基于交换的回溯】

1. 核心思想：用回溯算法生成全排列，通过 “确定当前位置元素 → 递归处理下一个位置 → 撤销当前选择” 的循环，遍历所有可能的排列。
2. 关键细节：
   • 递归终止条件是 first == n（所有位置都填完），此时要新建 ArrayList 存入结果，避免后续修改影响已保存的排列。
   • Collections.swap 是核心操作，用于 “选元素” 和 “撤销选元素”，实现回溯的核心逻辑。
    
3. 时间复杂度：O(n×n!)（n 是数组长度），n! 是全排列的总数，每个排列生成需要 O (n) 时间。

class Solution {
    public List<List<Integer>> permute(int[] nums) {
        // 最终存储所有排列结果的二维列表
        List<List<Integer>> res = new ArrayList<List<Integer>>();

        // 把数组nums的元素转成List，方便后续交换操作
        List<Integer> output = new ArrayList<Integer>();
        for (int num : nums) {
            output.add(num);
        }

        int n = nums.length;
        // 调用回溯函数，从第0个位置开始排列
        backtrack(n, output, res, 0);
        return res;
    }
    // 总数n, 交换用的列表tmp，res存完整数据，first这次交换的左边最后一个元素
    public void backtrack(int n, List<Integer> tmp, List<List<Integer>> res, int first){
        // 换完了，存入res
        if(first==n) res.add(new ArrayList(tmp));

        for(int i=first;i<n;i++){
            // 交换tmp的第i个元素和第first个元素
            Collections.swap(tmp, first, i);
            // 继续递归
            backtrack(n, tmp, res, first+1);
            // 撤销交换
            Collections.swap(tmp, first, i);
        }
    }
}

 

【背！！！经典的回溯问题，我还不会】

关键点在于划分左右，再递归交换再恢复。