LeetCode.全排列（Java+回溯）

给定一个 没有重复 数字的序列，返回其所有可能的全排列。
示例:
输入: [1,2,3]
输出: [ [1,2,3], [1,3,2], [2,1,3], [2,3,1], [3,1,2], [3,2,1] ]

写法一：4ms
自己捣鼓的能过。

public class Permutations {
	List<List<Integer>> resList = new ArrayList<List<Integer>>();

	public List<List<Integer>> permute(int[] nums) {
		ArrayList<Integer> list = new ArrayList<>();
		HashSet<Integer> set = new HashSet<>();
		for (int i = 0; i < nums.length; i++) {
			set.add(nums[i]);
			list.add(nums[i]);
			dfs(nums, list, set, i);
			set.remove(nums[i]);
			list.remove(list.size() - 1);
		}
		return resList;

	}

	public void dfs(int[] nums, List<Integer> list, HashSet<Integer> set, int index) {
		if (list.size() == nums.length) {
			resList.add(new ArrayList<>(list));
			return;
		}
		if (index >= nums.length || list.size() > nums.length) {
			return;
		} else {
			for (int i = 0; i < nums.length; i++) {
				if (i == index) {
					continue;
				}
				if (!set.contains(nums[i])) {
					set.add(nums[i]);
					list.add(nums[i]);
					dfs(nums, list, set, i);
					set.remove(nums[i]);
					list.remove(list.size() - 1);
				}
			}
		}

	}
}

写法二：写法一 的改良版。2ms
去掉了很多不必要的代码，整合了一下。
1.考虑到特殊情况：如果数组长度为0，那么返回一个空列表
2.将数组元素的判重和加入，全部放入dfs中进行处理，去掉index代表的下标。
代码更简洁了一点。

public class Permutations2 {
	List<List<Integer>> resList = new ArrayList<List<Integer>>();

	public List<List<Integer>> permute(int[] nums) {
		if (nums.length == 0) {
			return new ArrayList<>();
		}
		dfs(nums, new ArrayList<>(), new HashSet<>());
		return resList;

	}

	public void dfs(int[] nums, List<Integer> list, HashSet<Integer> set) {
		if (list.size() == nums.length) {
			resList.add(new ArrayList<>(list));
			return;
		} else {
			for (int i = 0; i < nums.length; i++) {
				if (!set.contains(nums[i])) {
					set.add(nums[i]);
					list.add(nums[i]);
					dfs(nums, list, set);
					set.remove(nums[i]);
					list.remove(list.size() - 1);
				}
			}
		}

	}
}

写法三：

static void swap(List<?> list, int i, int j) ——在指定的列表中的指定位置上交换元素。

class Solution {
    public List<List<Integer>> permute(int[] nums) {
        List<List<Integer>> res = new ArrayList<List<Integer>>();

        List<Integer> output = new ArrayList<Integer>();
        for (int num : nums) {
            output.add(num);
        }

        int n = nums.length;
        backtrack(n, output, res, 0);
        return res;
    }

    public void backtrack(int n, List<Integer> output, List<List<Integer>> res, int first) {
        // 所有数都填完了
        if (first == n) {
            res.add(new ArrayList<Integer>(output));
        }
        for (int i = first; i < n; i++) {
            // 动态维护数组
            Collections.swap(output, first, i);
            // 继续递归填下一个数
            backtrack(n, output, res, first + 1);
            // 撤销操作
            Collections.swap(output, first, i);
        }
    }
}

end.