日韩无码专区无码一级三级片|91人人爱网站中日韩无码电影|厨房大战丰满熟妇|AV高清无码在线免费观看|另类AV日韩少妇熟女|中文日本大黄一级黄色片|色情在线视频免费|亚洲成人特黄a片|黄片wwwav色图欧美|欧亚乱色一区二区三区

RELATEED CONSULTING
相關(guān)咨詢
選擇下列產(chǎn)品馬上在線溝通
服務(wù)時間：8:30-17:00
你可能遇到了下面的問題
關(guān)閉右側(cè)工具欄

新聞中心

這里有您想知道的互聯(lián)網(wǎng)營銷解決方案
你知道嗎？子集問題也要去重了！

子集問題+去重

創(chuàng)新互聯(lián)專業(yè)為企業(yè)提供昔陽網(wǎng)站建設(shè)、昔陽做網(wǎng)站、昔陽網(wǎng)站設(shè)計(jì)、昔陽網(wǎng)站制作等企業(yè)網(wǎng)站建設(shè)、網(wǎng)頁設(shè)計(jì)與制作、昔陽企業(yè)網(wǎng)站模板建站服務(wù)，10多年昔陽做網(wǎng)站經(jīng)驗(yàn)，不只是建網(wǎng)站，更提供有價值的思路和整體網(wǎng)絡(luò)服務(wù)。

子集II

力扣題目鏈接：https://leetcode-cn.com/problems/subsets-ii/

給定一個可能包含重復(fù)元素的整數(shù)數(shù)組 nums，返回該數(shù)組所有可能的子集(冪集)。

說明：解集不能包含重復(fù)的子集。

示例:

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

思路

做本題之前一定要先做78.子集。

這道題目和78.子集區(qū)別就是集合里有重復(fù)元素了，而且求取的子集要去重。

那么關(guān)于回溯算法中的去重問題，在40.組合總和II中已經(jīng)詳細(xì)講解過了，和本題是一個套路。

劇透一下，后期要講解的排列問題里去重也是這個套路，所以理解“樹層去重”和“樹枝去重”非常重要。

用示例中的[1, 2, 2] 來舉例，如圖所示：(注意去重需要先對集合排序)

子集II

從圖中可以看出，同一樹層上重復(fù)取2 就要過濾掉，同一樹枝上就可以重復(fù)取2，因?yàn)橥粯渲ι显氐募喜攀俏ㄒ蛔蛹?

本題就是其實(shí)就是78.子集的基礎(chǔ)上加上了去重，去重我們在40.組合總和II也講過了，所以我就直接給出代碼了：

C++代碼如下：

 
 
 
 
      
  
  
  
  1. class Solution { 
    2.   
  
  
  
  2. private: 
    3.   
  
  
  
  3.     vector> result; 
    4.   
  
  
  
  4.     vector path; 
    5.   
  
  
  
  5.     void backtracking(vector& nums, int startIndex, vector& used) { 
    6.   
  
  
  
  6.         result.push_back(path); 
    7.   
  
  
  
  7.         for (int i = startIndex; i < nums.size(); i++) { 
    8.   
  
  
  
  8.             // used[i - 1] == true，說明同一樹支candidates[i - 1]使用過 
    9.   
  
  
  
  9.             // used[i - 1] == false，說明同一樹層candidates[i - 1]使用過 
    10.   
  
  
  
  10.             // 而我們要對同一樹層使用過的元素進(jìn)行跳過 
    11.   
  
  
  
  11.             if (i > 0 && nums[i] == nums[i - 1] && used[i - 1] == false) { 
    12.   
  
  
  
  12.                 continue; 
    13.   
  
  
  
  13.             } 
    14.   
  
  
  
  14.             path.push_back(nums[i]); 
    15.   
  
  
  
  15.             used[i] = true; 
    16.   
  
  
  
  16.             backtracking(nums, i + 1, used); 
    17.   
  
  
  
  17.             used[i] = false; 
    18.   
  
  
  
  18.             path.pop_back(); 
    19.   
  
  
  
  19.         } 
    20.   
  
  
  
  20.     } 
    21.   
  
  
  
  21.  
    22.   
  
  
  
  22. public: 
    23.   
  
  
  
  23.     vector> subsetsWithDup(vector& nums) { 
    24.   
  
  
  
  24.         result.clear(); 
    25.   
  
  
  
  25.         path.clear(); 
    26.   
  
  
  
  26.         vector used(nums.size(), false); 
    27.   
  
  
  
  27.         sort(nums.begin(), nums.end()); // 去重需要排序 
    28.   
  
  
  
  28.         backtracking(nums, 0, used); 
    29.   
  
  
  
  29.         return result; 
    30.   
  
  
  
  30.     } 
    31.   
  
  
  
  31. }; 
    32.

使用set去重的版本。

 
 
 
 
      
  
  
  
  1. class Solution { 
    2.   
  
  
  
  2. private: 
    3.   
  
  
  
  3.     vector> result; 
    4.   
  
  
  
  4.     vector path; 
    5.   
  
  
  
  5.     void backtracking(vector& nums, int startIndex, vector& used) { 
    6.   
  
  
  
  6.         result.push_back(path); 
    7.   
  
  
  
  7.         unordered_set uset; 
    8.   
  
  
  
  8.         for (int i = startIndex; i < nums.size(); i++) { 
    9.   
  
  
  
  9.             if (uset.find(nums[i]) != uset.end()) { 
    10.   
  
  
  
  10.                 continue; 
    11.   
  
  
  
  11.             } 
    12.   
  
  
  
  12.             uset.insert(nums[i]); 
    13.   
  
  
  
  13.             path.push_back(nums[i]); 
    14.   
  
  
  
  14.             backtracking(nums, i + 1, used); 
    15.   
  
  
  
  15.             path.pop_back(); 
    16.   
  
  
  
  16.         } 
    17.   
  
  
  
  17.     } 
    18.   
  
  
  
  18.  
    19.   
  
  
  
  19. public: 
    20.   
  
  
  
  20.     vector> subsetsWithDup(vector& nums) { 
    21.   
  
  
  
  21.         result.clear(); 
    22.   
  
  
  
  22.         path.clear(); 
    23.   
  
  
  
  23.         vector used(nums.size(), false); 
    24.   
  
  
  
  24.         sort(nums.begin(), nums.end()); // 去重需要排序 
    25.   
  
  
  
  25.         backtracking(nums, 0, used); 
    26.   
  
  
  
  26.         return result; 
    27.   
  
  
  
  27.     } 
    28.   
  
  
  
  28. }; 
    29.

補(bǔ)充

本題也可以不適用used數(shù)組來去重，因?yàn)檫f歸的時候下一個startIndex是i+1而不是0。

如果要是全排列的話，每次要從0開始遍歷，為了跳過已入棧的元素，需要使用used。

代碼如下：

 
 
 
 
      
  
  
  
  1. class Solution { 
    2.   
  
  
  
  2. private: 
    3.   
  
  
  
  3.     vector> result; 
    4.   
  
  
  
  4.     vector path; 
    5.   
  
  
  
  5.     void backtracking(vector& nums, int startIndex) { 
    6.   
  
  
  
  6.         result.push_back(path); 
    7.   
  
  
  
  7.         for (int i = startIndex; i < nums.size(); i++) { 
    8.   
  
  
  
  8.             // 而我們要對同一樹層使用過的元素進(jìn)行跳過 
    9.   
  
  
  
  9.             if (i > startIndex && nums[i] == nums[i - 1] ) { // 注意這里使用i > startIndex 
    10.   
  
  
  
  10.                 continue; 
    11.   
  
  
  
  11.             } 
    12.   
  
  
  
  12.             path.push_back(nums[i]); 
    13.   
  
  
  
  13.             backtracking(nums, i + 1); 
    14.   
  
  
  
  14.             path.pop_back(); 
    15.   
  
  
  
  15.         } 
    16.   
  
  
  
  16.     } 
    17.   
  
  
  
  17.  
    18.   
  
  
  
  18. public: 
    19.   
  
  
  
  19.     vector> subsetsWithDup(vector& nums) { 
    20.   
  
  
  
  20.         result.clear(); 
    21.   
  
  
  
  21.         path.clear(); 
    22.   
  
  
  
  22.         sort(nums.begin(), nums.end()); // 去重需要排序 
    23.   
  
  
  
  23.         backtracking(nums, 0); 
    24.   
  
  
  
  24.         return result; 
    25.   
  
  
  
  25.     } 
    26.   
  
  
  
  26. }; 
    27.

總結(jié)

其實(shí)這道題目的知識點(diǎn)，我們之前都講過了，如果之前講過的子集問題和去重問題都掌握的好，這道題目應(yīng)該分分鐘AC。

當(dāng)然本題去重的邏輯，也可以這么寫

 
 
 
 
      
  
  
  
  1. if (i > startIndex && nums[i] == nums[i - 1] ) { 
    2.   
  
  
  
  2.         continue; 
    3.   
  
  
  
  3. } 
    4.

其他語言版本

Java

 
 
 
 
      
  
  
  
  1. class Solution { 
    2.   
  
  
  
  2.    List> result = new ArrayList<>();// 存放符合條件結(jié)果的集合 
    3.   
  
  
  
  3.    LinkedList path = new LinkedList<>();// 用來存放符合條件結(jié)果 
    4.   
  
  
  
  4.    boolean[] used; 
    5.   
  
  
  
  5.     public List> subsetsWithDup(int[] nums) { 
    6.   
  
  
  
  6.         if (nums.length == 0){ 
    7.   
  
  
  
  7.             result.add(path); 
    8.   
  
  
  
  8.             return result; 
    9.   
  
  
  
  9.         } 
    10.   
  
  
  
  10.         Arrays.sort(nums); 
    11.   
  
  
  
  11.         used = new boolean[nums.length]; 
    12.   
  
  
  
  12.         subsetsWithDupHelper(nums, 0); 
    13.   
  
  
  
  13.         return result; 
    14.   
  
  
  
  14.     } 
    15.   
  
  
  
  15.  
    16.   
  
  
  
  16.     private void subsetsWithDupHelper(int[] nums, int startIndex){ 
    17.   
  
  
  
  17.         result.add(new ArrayList<>(path)); 
    18.   
  
  
  
  18.         if (startIndex >= nums.length){ 
    19.   
  
  
  
  19.             return; 
    20.   
  
  
  
  20.         } 
    21.   
  
  
  
  21.         for (int i = startIndex; i < nums.length; i++){ 
    22.   
  
  
  
  22.             if (i > 0 && nums[i] == nums[i - 1] && !used[i - 1]){ 
    23.   
  
  
  
  23.                 continue; 
    24.   
  
  
  
  24.             } 
    25.   
  
  
  
  25.             path.add(nums[i]); 
    26.   
  
  
  
  26.             used[i] = true; 
    27.   
  
  
  
  27.             subsetsWithDupHelper(nums, i + 1); 
    28.   
  
  
  
  28.             path.removeLast(); 
    29.   
  
  
  
  29.             used[i] = false; 
    30.   
  
  
  
  30.         } 
    31.   
  
  
  
  31.     } 
    32.   
  
  
  
  32. } 
    33.

Python

 
 
 
 
      
  
  
  
  1. class Solution: 
    2.   
  
  
  
  2.     def subsetsWithDup(self, nums: List[int]) -> List[List[int]]: 
    3.   
  
  
  
  3.         res = []  #存放符合條件結(jié)果的集合 
    4.   
  
  
  
  4.         path = []  #用來存放符合條件結(jié)果 
    5.   
  
  
  
  5.         def backtrack(nums,startIndex): 
    6.   
  
  
  
  6.             res.append(path[:]) 
    7.   
  
  
  
  7.             for i in range(startIndex,len(nums)): 
    8.   
  
  
  
  8.                 if i > startIndex and nums[i] == nums[i - 1]:  #我們要對同一樹層使用過的元素進(jìn)行跳過 
    9.   
  
  
  
  9.                     continue 
    10.   
  
  
  
  10.                 path.append(nums[i]) 
    11.   
  
  
  
  11.                 backtrack(nums,i+1)  #遞歸 
    12.   
  
  
  
  12.                 path.pop()  #回溯 
    13.   
  
  
  
  13.         nums = sorted(nums)  #去重需要排序 
    14.   
  
  
  
  14.         backtrack(nums,0) 
    15.   
  
  
  
  15.         return res 
    16.

Go

 
 
 
 
      
  
  
  
  1. var res[][]int 
    2.   
  
  
  
  2. func subsetsWithDup(nums []int)[][]int { 
    3.   
  
  
  
  3.  res=make([][]int,0) 
    4.   
  
  
  
  4.   sort.Ints(nums) 
    5.   
  
  
  
  5.  dfs([]int{},nums,0) 
    6.   
  
  
  
  6.  return res 
    7.   
  
  
  
  7. } 
    8.   
  
  
  
  8. func dfs(temp, num []int, start int)  { 
    9.   
  
  
  
  9.  tmp:=make([]int,len(temp)) 
    10.   
  
  
  
  10.  copy(tmp,temp) 
    11.   
  
  
  
  11.  
    12.   
  
  
  
  12.  res=append(res,tmp) 
    13.   
  
  
  
  13.  for i:=start;i  
  
  
  
  14.   if i>start&&num[i]==num[i-1]{ 
    15.   
  
  
  
  15.    continue 
    16.   
  
  
  
  16.   } 
    17.   
  
  
  
  17.   temp=append(temp,num[i]) 
    18.   
  
  
  
  18.   dfs(temp,num,i+1) 
    19.   
  
  
  
  19.   temp=temp[:len(temp)-1] 
    20.   
  
  
  
  20.  } 
    21.   
  
  
  
  21. } 
    22.

Javascript

 
 
 
 
      
  
  
  
  1. var subsetsWithDup = function(nums) { 
    2.   
  
  
  
  2.     let result = [] 
    3.   
  
  
  
  3.     let path = [] 
    4.   
  
  
  
  4.     let sortNums = nums.sort((a, b) => { 
    5.   
  
  
  
  5.         return a - b 
    6.   
  
  
  
  6.     }) 
    7.   
  
  
  
  7.     function backtracing(startIndex, sortNums) { 
    8.   
  
  
  
  8.         result.push(path.slice(0)) 
    9.   
  
  
  
  9.         if(startIndex > nums.length - 1) { 
    10.   
  
  
  
  10.             return 
    11.   
  
  
  
  11.         } 
    12.   
  
  
  
  12.         for(let i = startIndex; i < nums.length; i++) { 
    13.   
  
  
  
  13.             if(i > startIndex && nums[i] === nums[i - 1]) { 
    14.   
  
  
  
  14.                 continue 
    15.   
  
  
  
  15.             } 
    16.   
  
  
  
  16.             path.push(nums[i]) 
    17.   
  
  
  
  17.             backtracing(i + 1, sortNums) 
    18.   
  
  
  
  18.             path.pop() 
    19.   
  
  
  
  19.         } 
    20.   
  
  
  
  20.     } 
    21.   
  
  
  
  21.     backtracing(0, sortNums) 
    22.   
  
  
  
  22.     return result 
    23.   
  
  
  
  23. }; 
    24.

新聞名稱：你知道嗎？子集問題也要去重了！
轉(zhuǎn)載源于：http://www.5511xx.com/article/cdchssd.html