全排列
题目描述
给定一个没有重复数字的序列，返回其所有可能的全排列。
示例:
输入: [1,2,3]
输出:
[
[1,2,3],
[1,3,2],
[2,1,3],
[2,3,1],
[3,1,2],
[3,2,1]
]
思路
dfs+回溯的模板题，，，，，，，，，，
Java实现
public List<List<Integer>> permute(int[] nums) {
List<List<Integer>> lists = new ArrayList<>();
if(nums.length==0){
return lists;
}
List<Integer> list = new ArrayList<>();
boolean[] flag = new boolean[nums.length];
dfs(lists,flag,0,nums.length,list,nums);
return lists;
}
private void dfs(List<List<Integer>> lists, boolean[] flag, int k, int length, List<Integer> list, int[] nums) {
if(k==length){
lists.add(new ArrayList<>(list));
return;
}
for(int i=0;i<length;i++){
if(flag[i]==false){
flag[i]=true;
list.add(nums[i]);
dfs(lists,flag,k+1,length,list,nums);
list.remove(list.size() - 1);
flag[i]=false;
}
}
}
执行用时 :1 ms, 在所有 Java 提交中击败了100.00%的用户
内存消耗 :36.5 MB, 在所有 Java 提交中击败了94.01%的用户
