题目描述
给出一组数字，返回该组数字的所有排列
例如：
[1,2,3]的所有排列如下[1,2,3],[1,3,2],[2,1,3],[2,3,1],[3,1,2], [3,2,1].（以数字在数组中的位置靠前为优先级，按字典序排列输出。）
算法思路
回溯法经典算法
num表示给出的数组，
path表示已经选择的数字
首先从num中的第一个元素开始向下做深度搜素，如果num遇到path中的有的元素则剪枝，path中的元素和num中的元素相等则找到一组解。找到最优解后取消选择向上回溯。
代码实现
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
import java.util.*;
public class Solution {
ArrayList<ArrayList<Integer>> res = new ArrayList<>();
public ArrayList<ArrayList<Integer>> permute(int[] num) {
ArrayList<Integer> path = new ArrayList<>();
dfs(num, path);
return res;
}
private void dfs(int[] num, ArrayList<Integer> path){
if(num.length == path.size()){
res.add(new ArrayList<Integer>(path));
return;
}
for(int i = 0; i < num.length; i++){
if(path.contains(num[i])){
continue;
}
path.add(num[i]);
dfs(num, path);
path.remove(path.size() - 1);
}
}
}