forked from walnutown/CodingInTheDeep
-
Notifications
You must be signed in to change notification settings - Fork 0
Expand file tree
/
Copy pathPermutations.java
More file actions
32 lines (28 loc) · 978 Bytes
/
Copy pathPermutations.java
File metadata and controls
32 lines (28 loc) · 978 Bytes
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
28
29
30
31
/*
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].
*/
// DFS, skip visited numbers
// time: O(n^2)
public class Solution {
public ArrayList<ArrayList<Integer>> permute(int[] num) {
ArrayList<ArrayList<Integer>> res = new ArrayList<ArrayList<Integer>>();
if (num == null || num.length == 0) return res;
finder(num, 0, res, new ArrayList<Integer>());
return res;
}
public void finder(int[] num, int dep, ArrayList<ArrayList<Integer>> res, ArrayList<Integer> r){
if (dep == num.length){
res.add(new ArrayList<Integer>(r));
return;
}
for (int i = 0; i < num.length; i++){
if (r.contains(num[i])) continue;
r.add(num[i]);
finder(num, dep+1, res, r);
r.remove(r.size()-1);
}
}
}