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

题意

列出数组中元素全排列

思路

这道题应该可以用next permutaion来解，这里我用的是DFS

 1 public class Solution {
 2     private boolean isVisited[];
 3     
 4     public List<List<Integer>> permute(int[] num) {   
 5         isVisited = new boolean[num.length];
 6         List<List<Integer>> result = new ArrayList<List<Integer>>();
 7         dfs(result, num, 0, new ArrayList<Integer>());
 8         
 9         return result;
10     }
11     
12     /**
13      * 深度遍历数组
14      * @param num
15      * @param dep
16      */
17     private void dfs(List<List<Integer>> result, int num[], int dep, List<Integer> cur){
18         if(dep != num.length){
19             for(int i = 0; i < num.length; i++){
20                 if(isVisited[i] == false){
21                     isVisited[i] = true;
22                     cur.add(num[i]);
23                     dfs(result, num, dep + 1, cur);
24                     isVisited[i] = false;
25                     cur.remove(cur.size() - 1);
26                 }//if
27             }//for
28         }//if
29         else{
30             result.add(new ArrayList<Integer>(cur));
31         }
32     }
33 }