要求:给定一个数字列表,返回其所有可能的排列。
样例
给出一个列表[1,2,3],其全排列为:
[
[1,2,3],
[1,3,2],
[2,1,3],
[2,3,1],
[3,1,2],
[3,2,1]
]
思路:我们首先想到的是使用递归来实现,递归里面利用了回溯法和深度优先搜索。假如有1,2,3,那么第一层递归的第一层循环里会往list里面加入1,调用第二层递归加入2,同样第三层递归加入了3,第四层递归已经加满了数,没有再加入数,直接返回,则执行第三层的remove一个数,执行第二层的remove,再递归加入3,递归里面再递归加入2,然后再remove 2,remove 3,remove 1,第一层递归第二次循环里加入2,递归加入1,再递归加入3,依次类推。
所以递归代码如下:
class Solution { /** * @param nums: A list of integers. * @return: A list of permutations. */ public List<List> permute(int[] nums) { List<List> res = new ArrayList<>(); if(nums == null) return res; if(nums.length == 0) { res.add(new ArrayList()); return res; } ArrayListlist = new ArrayList<>(); dfs(res, list, nums); return res; } private void dfs(List<List> res, ArrayListlist, int[] nums) { int n = nums.length; if(list.size() == n) { res.add(new ArrayList(list)); return; } for(int i = 0;i < n;i++) { if(list.contains(nums[i])) continue; list.add(nums[i]); dfs(res, list, nums); list.remove(list.size() - 1); } } }
还有一种非递归实现的方法,思路如下:也就是使用插入法,假如传进去的数字是1,2,3,那么先把1放进去list中得到【1】,把【1】放到list(存放list的list)中得到【【1】】然后取出【【1】】里面的第一个list【1】,往里面插入2,这个数字,有两种插法,就产生了两种排列【1,2】【2,1】,放进去得到【【1,2】,【2,1】】,然后取出【1,2】,插入3,有三种情况【3,1,2】,【1,3,2】,【1,2,3】,把它们放进去就是【【2,1】,【3,1,2】,【1,3,2】,【1,2,3】】,接着把【2,1】取出来,将3插进去,也有3中插法,就得到了最后的排列【【3,1,2】,【1,3,2】,【1,2,3】,【3,2,1】,【2,3,1】,【2,1,3】】,直到这里数组中的元素已经全部插入完毕。
代码如下:
class Solution { /** * @param nums: A list of integers. * @return: A list of permutations. */ public List<List> permute(int[] nums) { List<List> res = new ArrayList<List>(); if ( nums == null) return res; if( nums.length == 0) { res.add(new ArrayList()); return res; } Listlist = new ArrayList<>(); list.add(nums[0]); res.add(new ArrayList(list)); for(int i=1;i<nums.length;i++) { int size1 = res.size(); for(int j=0;j<size1;j++) { int size2 = res.get(0).size(); for(int k=0;k<=size2;k++) { ArrayListtemp = new ArrayList<>(res.get(0)); temp.add(k,nums[i]); res.add(temp); } res.remove(0); } } return res; } }
如果有所帮助,脸皮厚求个赞~
此文章仅代表自己(本菜鸟)学习积累记录,或者学习笔记,如有侵权,请联系作者删除。人无完人,文章也一样,文笔稚嫩,在下不才,勿喷,如果有错误之处,还望指出,感激不尽~
技术之路不在一时,山高水长,纵使缓慢,驰而不息。
公众号:秦怀杂货店