小学生都能看懂的题解 | #没有重复项数字的全排列#
没有重复项数字的全排列
https://www.nowcoder.com/practice/4bcf3081067a4d028f95acee3ddcd2b1
问题说明
我们需要找出一个数组中所有可能的顺序排列。例如,给定数组 [1, 2, 3]
,我们需要找出所有可能的排列组合:
[1, 2, 3]
[1, 3, 2]
[2, 1, 3]
[2, 3, 1]
[3, 1, 2]
[3, 2, 1]
解决方案
我们可以像玩拼图一样,一步一步地尝试不同的数字组合。想象你有一盒数字卡片,每次选择一张卡片放在一个空位上,直到所有的卡片都被用完为止。
步骤分解
- 创建一个空的排列组合列表:
- 用来存放所有可能的排列组合。
- 创建一个临时列表:
- 用来记录当前正在构建的排列。
- 递归地尝试所有可能性:
- 如果当前排列已经包含了所有的数字,那么就把它添加到排列组合列表中。
- 否则,遍历数组中的每一个数字:如果这个数字还没有被用过,那么就把它加入到当前排列中。
- 然后继续递归地尝试剩下的数字。
- 当返回时,把刚才加入的数字移除,恢复原状。
代码实现
现在让我们用 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); } } } } }
如果这篇文章对你有帮助,请点个免费的赞👍,让它能够帮助更多的人。
#题解#小学生都能看懂的算法 文章被收录于专栏
主要面向小白的算法文章。以小学生都能看懂为目标而编写,顺便巩固下自己。