LeetCode - Medium - 90. Subsets II

桃扇骨 2023-01-15 03:43 107阅读 0赞

## Topic ##

*  Array
 *  Backtracking

## Description ##

[https://leetcode.com/problems/subsets-ii/][https_leetcode.com_problems_subsets-ii]

Given an integer array `nums` that may contain duplicates, return all possible subsets (the power set).

The solution set **must not** contain duplicate subsets. Return the solution in **any order**.

**Example 1:**

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

**Example 2:**

Input: nums = [0]
    Output: [[],[0]]

**Constraints:**

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

## Analysis ##

本题与[LeetCode - Medium - 78. Subsets][]类似，区别在于解法多了排序原数组和跳过重复元素。

用示例中的\[1, 2, 2\] 来举例，如图所示：（「注意去重需要先对集合排序」）

![a388616952b76a18a2463b2dc667537a.png][]

从图中可以看出，同一树层上重复取2 就要过滤掉，同一树枝上就可以重复取2，因为同一树枝上元素的集合才是唯一子集！

### 参考文献 ###

1.  [回溯算法：求子集问题（二）][Link 1]

## Submission ##

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

## Test ##

import static org.junit.Assert.*;
    
    import java.util.Arrays;
    import java.util.List;
    
    import static org.hamcrest.collection.IsIterableContainingInAnyOrder.*;
    import org.junit.Test;
    
    public class SubsetsIITest { 
    
    	@Test
    	@SuppressWarnings("unchecked")
    	public void test() { 
    		SubsetsII obj = new SubsetsII();
    
    		
    		List<List<Integer>> result = obj.subsetsWithDup(new int[] { 1, 2, 2});
    		System.out.println(result);
    		assertThat(result, // 
    				containsInAnyOrder(Arrays.asList(), Arrays.asList(1), Arrays.asList(1, 2), //
    						Arrays.asList(1, 2, 2), Arrays.asList(2), Arrays.asList(2, 2)));
    		
    		assertThat(obj.subsetsWithDup(new int[] { 0}), //
    				containsInAnyOrder(Arrays.asList(), Arrays.asList(0)));
    		
    	}
    }

[https_leetcode.com_problems_subsets-ii]: https://leetcode.com/problems/subsets-ii/
[LeetCode - Medium - 78. Subsets]: https://blog.csdn.net/u011863024/article/details/115315615
[a388616952b76a18a2463b2dc667537a.png]: /images/20221022/d9b1b201e0cd4de194c428bc06475cea.png
[Link 1]: https://mp.weixin.qq.com/s?__biz=MzUxNjY5NTYxNA==&mid=2247485446&idx=1&sn=ef48986a30c3ed0e8e116dfd8fca93db&scene=21#wechat_redirect