题目描述
给定一个没有重复数字的序列,返回其所有可能的全排列。
样例
输入: [1,2,3]
输出:
[
[1,2,3],
[1,3,2],
[2,1,3],
[2,3,1],
[3,1,2],
[3,2,1]
]
算法1
时间复杂度
参考文献
Java 代码
class Solution {
List<Boolean> flag =null;
List<Integer> path =null;
public List<List<Integer>> permute(int[] num) {
flag = new ArrayList<>();
path = new ArrayList<>();
List<List<Integer>> ans = new ArrayList<>();
for(int i = 0;i<num.length;i++){
flag.add(false);
}
dfs(num,0,ans);
return ans;
}
public void dfs(int[] num,int u,List<List<Integer>> ans){
if(num.length == u){
List<Integer> pathList = new ArrayList<>(path.size());
pathList.addAll(path);
ans.add(pathList);
return;
}
for(int i=0;i<num.length;i++){
if(!flag.get(i)){
flag.set(i,true);
path.add(num[i]);
dfs(num,u+1,ans);
flag.set(i,false);
path.remove(path.size()-1);
}
}
}
}
参考大学菜站长的代码,明天自己再实现一遍