LeetCode - Medium - 47. Permutations II

喜欢ヅ旅行 2023-01-13 10:25 103阅读 0赞

## Topic ##

*  Backtracking

## Description ##

[https://leetcode.com/problems/permutations-ii/][https_leetcode.com_problems_permutations-ii]

Given a collection of numbers, nums, that might contain duplicates, return all possible unique permutations in any order.

**Example 1:**

Input: nums = [1,1,2]
    Output:
    [[1,1,2],
    [1,2,1],
    [2,1,1]]

**Example 2:**

Input: nums = [1,2,3]
    Output: [[1,2,3],[1,3,2],[2,1,3],[2,3,1],[3,1,2],[3,2,1]]

**Constraints:**

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

## Analysis ##

### 回溯算法 ###

与[LeetCode - Medium - 46. Permutations][]类似，不同之处在于给定一个可包含重复数字的序列，要返回所有不重复的全排列，这里涉及到去重。

去重一定要对元素进行排序，这样我们才方便通过相邻的节点来判断是否重复使用。

以示例中的 \[1,1,2\]为例 （为了方便举例，已经排序）抽象为一棵树，去重过程如图：

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3UwMTE4NjMwMjQ_size_16_color_FFFFFF_t_70_pic_center]

图中我们对同一树层，前一位（也就是nums\[i-1\]）如果使用过，那么就进行去重。

### 拓展 ###

去重最为关键的代码为：

if (used[i] || i > 0 && nums[i - 1] == nums[i] && !used[i - 1])
    	continue;

如果将!used\[i - 1\]改成 used\[i - 1\]， 结果也是正确的！**很神奇**。

if (used[i] || i > 0 && nums[i - 1] == nums[i] && used[i - 1])
    	continue;

这是为什么呢，就是上面我刚说的，如果要对树层中前一位去重，就用!used\[i - 1\]。如果要对树枝前一位去重用used\[i - 1\]。

**对于排列问题，树层上去重和树枝上去重，都是可以的，但是树层上去重效率更高！**

用\[1,1\] 来举一个例子。

树层上去重(!used\[i - 1\])，的树形结构如下：

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3UwMTE4NjMwMjQ_size_16_color_FFFFFF_t_70_pic_center 1]

树枝上去重（used\[i - 1\]）的树型结构如下：

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3UwMTE4NjMwMjQ_size_16_color_FFFFFF_t_70_pic_center 2]

用\[1,1,1\] **再**来举一个例子。

树层上去重(!used\[i - 1\])，的树形结构如下：

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3UwMTE4NjMwMjQ_size_16_color_FFFFFF_t_70_pic_center 3]  
树枝上去重（used\[i - 1\]）的树型结构如下：  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3UwMTE4NjMwMjQ_size_16_color_FFFFFF_t_70_pic_center 4]  
显然，树层上对前一位去重非常彻底，效率很高，树枝上对前一位去重虽然最后可以得到答案，但是做了很多无用搜索。

### 小结 ###

树层上去重要加上!used\[i - 1\]，似非而是，代码结合图加深理解吧！

### 参考 ###

1.  [回溯算法：排列问题（二）][Link 1]

## Submission ##

import java.util.ArrayList;
    import java.util.Arrays;
    import java.util.List;
    
    public class PermutationsII { 
    	public List<List<Integer>> permuteUnique(int[] nums) { 
    		List<List<Integer>> result = new ArrayList<>();
    		List<Integer> path = new ArrayList<>();
    		boolean[] used = new boolean[nums.length];
    		Arrays.sort(nums);
    		backtracking(path, nums, used, result);
    		return result;
    	}
    
    	private void backtracking(List<Integer> path, int[] nums, boolean[] used, List<List<Integer>> result) { 
    		if (path.size() == nums.length) { 
    			result.add(new ArrayList<>(path));
    			return;
    		}
    
    		for (int i = 0; i < nums.length; i++) { 
    			if (used[i] || i > 0 && nums[i - 1] == nums[i] && !used[i - 1])
    				continue;
    
    			used[i] = true;
    			path.add(nums[i]);
    			backtracking(path, nums, used, result);
    			path.remove(path.size() - 1);
    			used[i] = false;
    		}
    
    	}
    
    }

## Test ##

import static org.junit.Assert.*;
    
    import java.util.ArrayList;
    import java.util.Arrays;
    import java.util.List;
    
    import static org.hamcrest.collection.IsIterableContainingInAnyOrder.containsInAnyOrder;
    
    import org.hamcrest.Matcher;
    import org.junit.Test;
    
    @SuppressWarnings("unchecked")
    public class PermutationsIITest { 
    
    	private final int[] array1 = { 1, 1, 2};
    	private final int[] array2 = { 1, 2, 3};
    	private final int[] array3 = { 0, 1, 0, 0, 9};
    	
    	private final Matcher<Iterable<? extends List<Integer>>> expected1 = containsInAnyOrder(Arrays.asList(1,1,2), // 
    			Arrays.asList(1,2,1), Arrays.asList(2,1,1));
    	private final Matcher<Iterable<? extends List<Integer>>> expected2 = containsInAnyOrder(Arrays.asList(1,2,3), Arrays.asList(1,3,2),// 
    			Arrays.asList(2,1,3), Arrays.asList(2,3,1), Arrays.asList(3,1,2), Arrays.asList(3, 2, 1));
    	
    	private final String expected3String = "[0,0,0,1,9],[0,0,0,9,1],[0,0,1,0,9],[0,0,1,9,0],[0,0,9,0,1],"//
    									+ "[0,0,9,1,0],[0,1,0,0,9],[0,1,0,9,0],[0,1,9,0,0],[0,9,0,0,1],"//
    									+ "[0,9,0,1,0],[0,9,1,0,0],[1,0,0,0,9],[1,0,0,9,0],[1,0,9,0,0],"//
    									+ "[1,9,0,0,0],[9,0,0,0,1],[9,0,0,1,0],[9,0,1,0,0],[9,1,0,0,0]";
    		
    	private final Matcher<Iterable<? extends List<Integer>>> expected3 = containsInAnyOrder(string2IntegerList(expected3String));
    	
    	@Test
    	public void test() { 
    		PermutationsII obj = new PermutationsII();
    
    		assertThat(obj.permuteUnique(array1), expected1);
    		assertThat(obj.permuteUnique(array2), expected2);
    		assertThat(obj.permuteUnique(array3), expected3);
    	}
    	
    	private List<Integer>[] string2IntegerList(String original){ 
    		List<Integer>[] result;
    		original = original.substring(1, original.length() - 1);
    		String[] strs = original.split("\\],\\[");
    		result = new ArrayList[strs.length];
    		for(int i = 0; i < strs.length; i++) { 
    			String[] nums = strs[i].split(",");
    			List<Integer> list = new ArrayList<>();
    			for(String num : nums) { 
    				list.add(Integer.valueOf(num));
    			}
    			result[i] = list;
    		}
    		return result;
    	}
    	
    	
    	@Test
    	public void testString2IntegerList() { 
    		String str = "[0,0,0,1,9],[0,0,0,9,1],[0,0,1,0,9],[0,0,1,9,0],[0,0,9,1,0],"
    				+ "[0,0,9,0,1],[0,1,0,0,9],[0,1,0,9,0],[0,1,9,0,0],[0,9,0,1,0],"
    				+ "[0,9,0,0,1],[0,9,1,0,0],[0,9,0,1,0],[0,9,0,0,1],[1,0,0,0,9],"
    				+ "[1,0,0,9,0],[1,0,9,0,0],[1,9,0,0,0],[9,0,0,1,0],[9,0,0,0,1],"
    				+ "[9,0,1,0,0],[9,0,0,1,0],[9,0,0,0,1],[9,1,0,0,0],[9,0,0,1,0],"
    				+ "[9,0,0,0,1],[9,0,1,0,0],[9,0,0,1,0],[9,0,0,0,1]";
    		System.out.println(string2IntegerList(str));
    	}
    	
    }

[https_leetcode.com_problems_permutations-ii]: https://leetcode.com/problems/permutations-ii/
[LeetCode - Medium - 46. Permutations]: https://blog.csdn.net/u011863024/article/details/115483022
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3UwMTE4NjMwMjQ_size_16_color_FFFFFF_t_70_pic_center]: /images/20221022/de7a228b4d0c48dda67b932f8bba99c5.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3UwMTE4NjMwMjQ_size_16_color_FFFFFF_t_70_pic_center 1]: /images/20221022/a9881b5146ea4b0c959e4eaf25360656.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3UwMTE4NjMwMjQ_size_16_color_FFFFFF_t_70_pic_center 2]: /images/20221022/87e7c2ffd31e4266a2cbb7722fd7b483.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3UwMTE4NjMwMjQ_size_16_color_FFFFFF_t_70_pic_center 3]: /images/20221022/93494a727ac74b39813437bdc0625bd4.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3UwMTE4NjMwMjQ_size_16_color_FFFFFF_t_70_pic_center 4]: /images/20221022/b7877df286e04f6180638aa79a04a3f8.png
[Link 1]: https://mp.weixin.qq.com/s?__biz=MzUxNjY5NTYxNA==&mid=2247485514&idx=1&sn=29aa5828c0847fe39d2ea90804fba69e&scene=21#wechat_redirect