莆田人做的网站,广东省建设行业统一身份认证平台,wordpress无法选择数据库,装修案例标题怎么写#x1f4dd;个人主页#xff1a;五敷有你 #x1f525;系列专栏#xff1a;算法分析与设计
⛺️稳中求进#xff0c;晒太阳 题目 给定一个不含重复数字的整数数组 nums #xff0c;返回其 所有可能的全排列 。可以 按任意顺序 返回答案。 示例
示例 1#xff1… 个人主页五敷有你 系列专栏算法分析与设计
⛺️稳中求进晒太阳 题目 给定一个不含重复数字的整数数组 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]]
思路
回溯
这个问题可以看作是n个排列成一行的空格我们需要从左向右填入给定的n个数每个只能使用一次那么很直接的可以想到穷举法从左向右依次填入看能不能填完这个n个空格在这个过程可以使用回溯来模拟。
我们定义一个backtrack(first,output)表示从左向右填到first个位置当前排列为output,那么整个递归函数分为两个情况
一、firstn
这个情况就表示已经填完了n个位置可以进行一次排列的收集
二、firstn
这个情况是从第一个格到first是固定了之后就 之后first左边的固定了右边的还在回溯。
first现在指向2之后2和2自己进行交换有人可能回想为什么2还要与自己进行交换因为1 2 3 4 5 6 本身也是一种排列难道不是吗呼
然后first指向3同理自身与自身交换一次然后一直回溯。。。。
之后再回来回溯交换 for (int i first; i n; i) {// 动态维护数组Collections.swap(output, first, i);// 继续递归填下一个数backtrack(n, output, res, first 1);// 撤销操作Collections.swap(output, first, i);}
代码实现
class Solution {public ListListInteger permute(int[] nums) {ListListInteger res new ArrayListListInteger();ListInteger output new ArrayListInteger();for (int num : nums) {output.add(num);}int n nums.length;backtrack(n, output, res, 0);return res;}public void backtrack(int n, ListInteger output, ListListInteger res, int first) {// 所有数都填完了if (first n) {res.add(new ArrayListInteger(output));}for (int i first; i n; i) {// 动态维护数组Collections.swap(output, first, i);// 继续递归填下一个数backtrack(n, output, res, first 1);// 撤销操作Collections.swap(output, first, i);}}
}
运行结果
