Given a collection of numbers, return all possible permutations.
For example,[1,2,3]
have the following permutations:[1,2,3]
, [1,3,2]
, [2,1,3]
, [2,3,1]
, [3,1,2]
, and [3,2,1]
.
实现思想:
给定一个数组[1,2,3,4] 1、[1,[2,3,4]] ---------->[2,3,4]的子数组计算--->[2,[3,4]],[3,[2,4]]和[4[2,3]] 2、[2,[1,3,4]] 3、[3,[1,2,4]] 4、[4,[1,2,3]]
从上面可以看出,需要使递归的思想。
java代码实现如下:
import java.util.ArrayList; import java.util.Collection; import java.util.Iterator; import java.util.List; public class Solution { public List<List<Integer>> permute(int[] num) { List<List<Integer>> list = new ArrayList<>(); if(num.length == 1){ //当数据中只有一个元素时,只需要一种情况 List<Integer>lst = new ArrayList<>(); lst.add(num[0]); list.add(lst); } else{ for(int i = 0 ; i < num.length ; i++){ int[] num1 = new int[num.length-1]; int j = 0; int k = 0; while(j < num.length){ //while语句是用来得到当前数组的子数组 if(j != i){ num1[k++] = num[j++]; } else j++; } List<List<Integer>> list1 = permute(num1); Iterator<List<Integer>> it = list1.iterator(); while(it.hasNext()){ //取出子数组得到集合中与当前元素进行组成 List<Integer>lst = new ArrayList<>(); lst.add(num[i]); lst.addAll( it.next()); list.add(lst); } } } return list; } public static void main(String[] args) { // TODO Auto-generated method stub int[] num = {1,2,3}; System.out.println(new Solution().permute(num)); } }