小学生都能看懂的题解 | #没有重复项数字的全排列#

问题说明

我们需要找出一个数组中所有可能的顺序排列。例如，给定数组 [1, 2, 3]，我们需要找出所有可能的排列组合：

• [1, 2, 3]
• [1, 3, 2]
• [2, 1, 3]
• [2, 3, 1]
• [3, 1, 2]
• [3, 2, 1]

解决方案

我们可以像玩拼图一样，一步一步地尝试不同的数字组合。想象你有一盒数字卡片，每次选择一张卡片放在一个空位上，直到所有的卡片都被用完为止。

步骤分解

1. 创建一个空的排列组合列表：
1. 用来存放所有可能的排列组合。
2. 创建一个临时列表：
1. 用来记录当前正在构建的排列。
3. 递归地尝试所有可能性：
1. 如果当前排列已经包含了所有的数字，那么就把它添加到排列组合列表中。
2. 否则，遍历数组中的每一个数字：如果这个数字还没有被用过，那么就把它加入到当前排列中。
3. 然后继续递归地尝试剩下的数字。
4. 当返回时，把刚才加入的数字移除，恢复原状。

代码实现

现在让我们用 Java 代码来实现这个过程：

import java.util.ArrayList;

public class Solution {
    public ArrayList<ArrayList<Integer>> permute(int[] num) {
        ArrayList<ArrayList<Integer>> result = new ArrayList<>();
        // 创建一个临时列表来记录当前排列
        ArrayList<Integer> tempList = new ArrayList<>();
        // 调用递归函数来生成排列
        generatePermutations(result, tempList, num);
        return result;
    }

    private void generatePermutations(ArrayList<ArrayList<Integer>> result, ArrayList<Integer> tempList, int[] num) {
        if (tempList.size() == num.length) {
            // 如果当前排列已经包含了所有数字，就把它添加到结果列表中
            result.add(new ArrayList<>(tempList));
        } else {
            // 遍历数组中的每一个数字
            for (int i = 0; i < num.length; i++) {
                // 如果这个数字还没有被用过
                if (!tempList.contains(num[i])) {
                    // 把这个数字加入到当前排列中
                    tempList.add(num[i]);
                    // 继续尝试下一个数字
                    generatePermutations(result, tempList, num);
                    // 回溯：移除刚刚加入的数字，恢复原状
                    tempList.remove(tempList.size() - 1);
                }
            }
        }
    }
}

如果这篇文章对你有帮助，请点个免费的赞👍，让它能够帮助更多的人。