欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识!
您现在的位置是: 首页

46.全排列

程序员文章站 2022-07-08 15:56:52
...

1.题目

46.全排列

2.解法

class Solution {    
	public List<List<Integer>> permute(int[] nums) {        
		List<List<Integer>> aList = new LinkedList();        
		ArrayList<Integer> true_nums = new ArrayList<Integer>();        
		for (int i : nums) {            
			true_nums.add(i);        
		}       
		int len = nums.length;        
		backtrack(0, len, true_nums, aList);       
		return aList;    
		}
		
    public void backtrack(int first, int len, ArrayList<Integer> nums, 
    List<List<Integer>> aList) {       
    	 if (first == len) {           
    	  aList.add(new ArrayList<Integer>(nums));} 
        for (int i = first; i < len; i++) {           
        	 Collections.swap(nums, first, i);           
          	backtrack(first+1, len, nums, aList);           
          	 Collections.swap(nums, first, i);        
          	 }            
       }
 }

==时间复杂度46.全排列空间复杂度O(n!)

3.思考

这里是使用的回溯方法
1、当first==n时回溯结束 (终止条件)
2、nums数组中没有swap函数,所以为了方便运算,将nums放到ArrayList中
3、我不太理解List<List> aList = new LinkedList()可以作为引用,全局使用,
nums作为ArrayList,可以在每次回溯时随意改变,难道不会影响原值嘛。

相关标签: Leetcode打卡