public class Permutation {

	public static List<List<Integer>> permute(int[] nums) {
		
		List<Integer> visited = new ArrayList<Integer>();
		List<List<Integer>> res = new LinkedList<>();
		backtrack(nums,visited,res);
		return res;
		
	}
	
	private static void backtrack(int[] nums, List<Integer> visited,List<List<Integer>> res) {
		
		if (visited.size() == nums.length) {  // 结束条件
			res.add(new LinkedList<Integer>(visited));
			return;
		}
		
		for (int i = 0; i < nums.length; i++) { // 选择列表
			if (visited.contains(nums[i])) {
				continue;
			}
			visited.add(nums[i]); // 做选择
			backtrack(nums, visited, res);  // 下一层决策
			visited.remove(visited.size()-1); // 取消选择	
		}
	}
}

/*
output：
*/