回溯--46. 全排列/medium 理解度C

1、题目

给定一个不含重复数字的数组 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 中的所有整数 互不相同

2、题目分析

用递归解决问题时，通常是以2个角度来构思解决方案：自底向上、或自顶向下

本问题主要采用自顶向下的方式思考。（自顶向下，往往意味着在向下传递前先进行逻辑处理）

递归生成全排列访问数组。每次递归针对每个位置进行值的设置

3、复杂度最优解代码示例

List<List<Integer>> res = new ArrayList<>();
    public List<List<Integer>> permute(int[] nums) {
        // 全排列访问数组
        List<Integer> visit = new ArrayList<>();
        // 递归生成全排列访问数组。每次递归针对每个位置进行值的设置
        this.dfs(nums, visit);
        return res;
    }
    public void dfs(int[] nums, List<Integer> visit) {
        if (visit.size() == nums.length) {
            // 如果全排列已完成，则归集到结果中
            res.add(new ArrayList<>(visit));
            return;
        }

        for (int i = 0; i < nums.length; i++) {
            // 遍历设置 visit 当前最后位置的值
            if (visit.contains(nums[i])) {
                // 该值已存在于visit中，则不再设置
                continue;
            }

            // 将元素当前 index 位置
            visit.add(nums[i]);
            // 递归下一位置，index+1 位置的值
            this.dfs(nums,visit);
            // 回滚掉 index 位置的值
            visit.remove(visit.size() - 1);
        }
    }

4、适用场景

全排列的适用场景包括算法问题解决、数学组合分析、数据处理任务等。具体如下：

1. 算法竞赛和编程挑战：在算法竞赛或编程挑战中，经常会遇到需要生成一个集合的所有可能排列的问题。例如，求解一组不同元素的全部排列方式，或者找出满足某些特定条件的排列组合。
2. 密码学：全排列可以用于加密算法中，通过生成所有可能的密钥排列来尝试解密信息。
3. 数据分析：在数据分析过程中，可能需要对数据集进行全排列以观察数据在不同顺序下的表现，从而发现潜在的模式或关联。
4. 游戏开发：在游戏中，特别是在解谜游戏或策略游戏中，全排列可以用来生成关卡的不同难度版本，或者用于计算玩家的策略选择。
5. 数学研究：在数学研究中，全排列有助于解决组合数学中的问题，如计算多项式展开的系数、统计设计等领域的应用。
6. 优化问题：在某些优化问题中，可能需要穷举所有可能的解空间排列，以找到最优解或近似最优解。
7. 生物信息学：在基因序列分析中，全排列可以帮助科学家理解DNA序列的多样性和复杂性。
8. 化学：在化学中，全排列可以用来预测分子的可能结构，尤其是在药物设计和材料科学中。
9. 工业工程：在生产线的设计和优化中，全排列可以帮助工程师计算不同零件装配顺序的效率。

总的来说，全排列是一种强大的工具，它可以应用于多种领域和问题中，尤其是在需要探索所有可能性的情况下。