Permutations II

Java

public class Solution {
    /*
     * @param nums: A list of integers.
     * @return: A list of permutations.
     */
		public List<List<Integer>> permuteUnique(int[] nums) {
			List<List<Integer>> result = new ArrayList<>();
			List<Integer> path = new ArrayList<>();
			boolean[] visited = new boolean[nums.length];
			dfs(nums, result, path, visited);
			return result;
		}
		private void dfs(int[] nums, List<List<Integer>> result, List<Integer> path, boolean[] visited) {
			if (path.size() == nums.length) {
				result.add(new ArrayList<>(path));
			}
			for (int i = 0; i < nums.length; i++) {
				if (visited[i]) continue;
				
				//数字有可能不在一起
				boolean skip = false;
				for (int j = 0; j < i; j++) {
					if (nums[j] == nums[i] && !visited[j]) {
						skip = true;
						break;
					}
				}
				if (skip) continue;
				
				visited[i] = true;
				path.add(nums[i]);
				dfs(nums, result, path, visited);
				path.remove(path.size() - 1);
				visited[i] = false;
			}
		}
}


// 排序去重
public class Solution {
    /*
     * @param nums: A list of integers.
     * @return: A list of permutations.
     */
		public List<List<Integer>> permuteUnique(int[] nums) {
			List<List<Integer>> result = new ArrayList<>();
			List<Integer> path = new ArrayList<>();
			Arrays.sort(nums);
			boolean[] visited = new boolean[nums.length];
			dfs(nums, result, path, visited);
			return result;
		}
		private void dfs(int[] nums, List<List<Integer>> result, List<Integer> path, boolean[] visited) {
			if (path.size() == nums.length) {
				result.add(new ArrayList<>(path));
			}
			for (int i = 0; i < nums.length; i++) {
				if (visited[i]) continue;
				
		/*
				boolean skip = false;
				for (int j = 0; j < i; j++) {
					if (nums[j] == nums[i] && !visited[j]) {
						skip = true;
						break;
					}
				}
				if (skip) {
					continue;
				}
				*/
				
				//因为数组已经排序
				if (i > 0 && nums[i - 1] == nums[i] && !visited[i - 1]) {
					continue;
				}
				
				visited[i] = true;
				path.add(nums[i]);
				dfs(nums, result, path, visited);
				path.remove(path.size() - 1);
				visited[i] = false;
			}
		}
}