2015年9月21日星期一

Leetcode 46 Permutations

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].
Solution 1: recursive DFS

 public class Solution {  
   public List<List<Integer>> permute(int[] nums) {  
     List<List<Integer>> res=new ArrayList<>();  
     dfs(nums,0,res);  
     return res;  
   }  
   private void dfs(int[] nums, int d, List<List<Integer>> res) {  
     if (d==nums.length){  
       List<Integer> one=new ArrayList<>();  
       for (int i=0; i<nums.length; i++) one.add(nums[i]);  
       res.add(one);  
     }  
     else {  
       dfs(nums,d+1,res);  
       for (int i=d+1; i<nums.length; i++) {  
         swap(nums,d,i);  
         dfs(nums,d+1,res);  
         swap(nums,d,i);  
       }  
     }  
   }  
   private void swap(int[] nums, int i, int j) {  
     int temp=nums[i];  
     nums[i]=nums[j];  
     nums[j]=temp;  
   }  
 }  

Solution 2: iterative

没有评论:

发表评论