首页 > 代码库 > Leetcode-Permutations

Leetcode-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].

Have you met this question in a real interview?
 
Solution:
Use recursive method. This solution is a iterative recursive solution.
 1 public class Solution { 2     public List<List<Integer>> permute(int[] num) { 3         int len = num.length; 4         List<List<Integer>> resSet = new ArrayList<List<Integer>>(); 5         List<Integer> curSeq = new ArrayList<Integer>(); 6         boolean[] used = new boolean[len]; 7         Arrays.fill(used,false); 8         Arrays.sort(num); 9         int curIndex = 0;10         curSeq.add(-1);11         while (curIndex!=-1){12             if (curIndex==len){13                 List<Integer> temp = new ArrayList<Integer>();14                 for (int i=0;i<curSeq.size();i++) temp.add(num[curSeq.get(i)]);15                 resSet.add(temp);16                 curIndex--;17                 continue;18             }19             20             int val = -1;21             if (curSeq.size()>curIndex){22                 val = curSeq.get(curIndex);23                 if (val!=-1)24                     used[val]=false;25                 curSeq.remove(curIndex);26             }27 28             boolean find = false;29             for (int i=val+1;i<len;i++)30                 if (!used[i]){31                     used[i]=true;32                     curSeq.add(i);33                     curIndex++;34                     find = true;35                     break;36                 }37             38             if (find)39                 continue;40             else 41                 curIndex--;42         }43 44         return resSet;45     }46 }

 

Leetcode-Permutations