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].
Idea: Backtracking depth-first search. For each unused integer x, put it at the head of the permutation, mark x as used, then recursively construct the permutation from the rest of unused integers. When we roll back, do not forget to re-mark x to unused, since that x can be used at other positions in the future.
Time: O(n!) Space: O(n)
Code:
public class Solution {
public List<List<Integer>> permute(int[] num) {
List<List<Integer>> result=new ArrayList<List<Integer>>();
List<Integer> path=new ArrayList<Integer>();
boolean[] used=new boolean[num.length];
dfs(result,path,num);
return result;
}
public void dfs(List<List<Integer>> result,List<Integer> path,int[] num)
{
if(path.size()==num.length)
{
result.add(new ArrayList<Integer>(path));
return;
}
for(int i=0;i<num.length;i++)
{
if(path.contains(num[i])==false)
{
path.add(num[i]);
dfs(result,path,num);
path.remove(path.size()-1);
}
}
}
}
No comments:
Post a Comment