46. 全排列

class Solution {
	private LinkedList ans = new LinkedList<LinkedList>();
	private int n;
	private LinkedList<Integer> path = new LinkedList<Integer>();
	private boolean[] bool;
	
	public List<List<Integer>> permute(int[] nums) {
		n = nums.length;
		bool = new boolean[n];
		dfs(nums, 0);
		return ans;
	}

	private void dfs(int nums[], int u) {
		if (u == n) {
			ans.add(path.clone());                                           //记得克隆 不然之前保存的链表都是同一个 也就是递归出来之后都是remove 同一个 这也导致答案全部都是[[],[],[],[],[],[],[]]  
		} else {
			for (int i = 0; i < n; i++) {
				if (!bool[i]) {
					path.add(nums[i]);
					bool[i] = true;
					dfs(nums, u + 1);
					bool[i] = false;
					path.removeLast();                           //事实证明 Linked 所需要的空间大， 操作方便 而 ArrayList 空间小 而操作不方便
				}
			}
		}
	}
}