leetcode刷题(剑指offer)47.全排列Ⅱ

47.全排列Ⅱ

给定一个可包含重复数字的序列 nums ，按任意顺序 返回所有不重复的全排列。

示例 1：

输入：nums = [1,1,2] 输出： [[1,1,2], [1,2,1], [2,1,1]]

示例 2：

输入：nums = [1,2,3] 输出：[[1,2,3],[1,3,2],[2,1,3],[2,3,1],[3,1,2],[3,2,1]]

提示：

1 <= nums.length <= 8-10 <= nums[i] <= 10

题解：基于46题的基础上使用Set数据结构进行去重。

代码如下：

package com.offer; import com.sun.org.apache.bcel.internal.generic.IF_ACMPEQ; import java.util.ArrayList; import java.util.HashSet; import java.util.List; import java.util.Set; public class _47全排列Ⅱ { public static void main(String[] args) { int[] nums = new int[]{1, 2, 1}; System.out.println(permuteUnique(nums)); } private static boolean vis[]; public static List<List<Integer>> permuteUnique(int[] nums) { if (nums == null || nums.length == 0) { return new ArrayList<>(); } vis = new boolean[nums.length]; Set<List<Integer>> set = new HashSet<>(); dfs(0, nums, set, new ArrayList<>()); return new ArrayList<>(set); } private static void dfs(int t, int[] nums, Set<List<Integer>> res, List<Integer> path) { if (t == nums.length) { res.add(new ArrayList<>(path)); return; } for (int i = 0; i < nums.length; i++) { if (!vis[i]) { vis[i] = true; path.add(nums[i]); dfs(t + 1, nums, res, path); // 移除最后一个 path.remove(t); vis[i] = false; } } } }