Given a collection of distinct 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].
Initial Though
基本上的概念就是對一個 input integer array 做隨機排序，使個 Backtracking 的經典題目。
Guide
這裡可以想像就是在對一個 N-ary Tree 用 DFS 來遍歷， 而 N 就是總共所有的 integer array。所以可以想像每下一層就是要從剩下的數字中挑一個放到 sub，所以這裡我用一個 HashSet 來記錄已經取出的數字。如此做到所有的數字都被拿完，也就是 sub 和 input array 一樣長，此時就把 sub clone 一份到 result 裡。並且回傳的時候要把自己放到 sub 尾端的數字 pop 掉，另外也要移除 HashSet 裡的同一個數字。這樣從底部回去的時候，之前選的字才能被之後 sub array 選到。
Code
public class Solution {
public List<List<Integer>> permute(int[] nums) {
List<List<Integer>> result = new ArrayList<List<Integer>>();
HashSet<Integer> h = new HashSet<Integer>();
LinkedList<Integer> sub = new LinkedList<Integer>();
DFS(nums,0,result,h,sub);
return result;
}
public void DFS(int[] nums, int k , List<List<Integer>> result, HashSet<Integer> h , LinkedList<Integer> sub){
if(k==nums.length){
result.add((List<Integer>)sub.clone());
return;
}
for(int i =0 ;i<nums.length;i++){
if(!h.contains(nums[i])){
sub.addLast(nums[i]);
h.add(nums[i]);
DFS(nums,k+1,result,h,sub);
int a = sub.removeLast();
h.remove(a);
}
}
}
}