給定一個可能包含重復元素的整數數組 nums，返回該數組所有可能的子集（冪集）。

說明：解集不能包含重復的子集。

示例:

輸入: [1,2,2]
輸出:
[
? [2],
? [1],
? [1,2,2],
? [2,2],
? [1,2],
? []
]

思路：相比第78題，本題重點在于去重

例如：[2,2,1,2,2]

1.選擇0，2，3位置的數字和1，2，3位置的數字是一樣的，這種的是順序，數字完全一樣

2.選擇0，2，3位置的數字和2，3，4位置的數字也是一樣的，這種的是數字一樣，但是順序不一樣

那首先想辦法消除第二種，直接給nums數組去重，這樣就不會出現第二種情況了

之后需要判斷當前數字和上一個數字是否相同，相同的話跳過即可。

提交的代碼：

class Solution {
? ?public static List<List<Integer>> subsetsWithDup(int[] nums) {
? ? ? ? Arrays.sort(nums);
? ? ? ? List<List<Integer>> result = new ArrayList();
? ? ? ? List<Integer> list = new ArrayList();
? ? ? ? result = find(0,nums,list,result);
? ? ? ? return result;
? ? }
? ? public static List<List<Integer>> find(int begin,int[] nums,List<Integer> list,List<List<Integer>> result)
? ? {
? ? ?? ?int i;
? ? ?? ?result.add(new ArrayList(list));
? ? ?? ?for(i=begin;i<nums.length;i++)
? ? ?? ?{
? ? ?? ??? ?if(i>begin&&nums[i]==nums[i-1])
? ? ?? ??? ?{
? ? ?? ??? ??? ?continue;
? ? ?? ??? ?}
? ? ?? ??? ?list.add(nums[i]);
? ? ?? ??? ?find(i+1,nums,list,result);
? ? ?? ??? ?list.remove(list.size()-1);
? ? ?? ?}
? ? ?? ?return result;
? ? }
}

完整的代碼：

import java.util.ArrayList;
import java.util.Arrays;
import java.util.Iterator;
import java.util.List;

public class Solution90 {
? ? public static List<List<Integer>> subsetsWithDup(int[] nums) {
? ? ? ? Arrays.sort(nums);
? ? ? ? List<List<Integer>> result = new ArrayList();
? ? ? ? List<Integer> list = new ArrayList();
? ? ? ? result = find(0,nums,list,result);
? ? ? ? return result;
? ? }
? ? public static List<List<Integer>> find(int begin,int[] nums,List<Integer> list,List<List<Integer>> result)
? ? {
? ? ?? ?int i;
? ? ?? ?result.add(new ArrayList(list));
? ? ?? ?for(i=begin;i<nums.length;i++)
? ? ?? ?{
? ? ?? ??? ?if(i>begin&&nums[i]==nums[i-1])
? ? ?? ??? ?{
? ? ?? ??? ??? ?continue;
? ? ?? ??? ?}
? ? ?? ??? ?list.add(nums[i]);
? ? ?? ??? ?find(i+1,nums,list,result);
? ? ?? ??? ?list.remove(list.size()-1);
? ? ?? ?}
? ? ?? ?return result;
? ? }
?? ?public static void main(String[] args)
?? ?{
?? ??? ?int[] nums = {1,2,2};
?? ??? ?List<List<Integer>> list = new ArrayList();
?? ??? ?list = subsetsWithDup(nums);
?? ??? ?Iterator<List<Integer>> it = list.iterator();
?? ??? ?while(it.hasNext()) {
?? ??? ??? ?Iterator<Integer> itt = it.next().iterator();
?? ??? ??? ?while(itt.hasNext()) {
?? ??? ??? ??? ?System.out.print(itt.next()+" ");
?? ??? ??? ?}
?? ??? ??? ?System.out.println();
?? ??? ?}
?? ?}
}
?

總結

以上是生活随笔為你收集整理的Leetcode--90. 子集Ⅱ的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。