[[427534]]

子集問題+去重

子集II

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

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

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

示例:

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

思路

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

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

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

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

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

子集II

從圖中可以看出，同一樹層上重復取2 就要過濾掉，同一樹枝上就可以重復取2，因為同一樹枝上元素的集合才是唯一子集!

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

C++代碼如下：

class Solution { 
private: 
    vector<vector<int>> result; 
    vector<int> path; 
    void backtracking(vector<int>& nums, int startIndex, vector<bool>& used) { 
        result.push_back(path); 
        for (int i = startIndex; i < nums.size(); i++) { 
            // used[i - 1] == true，說明同一樹支candidates[i - 1]使用過 
            // used[i - 1] == false，說明同一樹層candidates[i - 1]使用過 
            // 而我們要對同一樹層使用過的元素進行跳過 
            if (i > 0 && nums[i] == nums[i - 1] && used[i - 1] == false) { 
                continue; 
            } 
            path.push_back(nums[i]); 
            used[i] = true; 
            backtracking(nums, i + 1, used); 
            used[i] = false; 
            path.pop_back(); 
        } 
    } 
 
public: 
    vector<vector<int>> subsetsWithDup(vector<int>& nums) { 
        result.clear(); 
        path.clear(); 
        vector<bool> used(nums.size(), false); 
        sort(nums.begin(), nums.end()); // 去重需要排序 
        backtracking(nums, 0, used); 
        return result; 
    } 
}; 

使用set去重的版本。

class Solution { 
private: 
    vector<vector<int>> result; 
    vector<int> path; 
    void backtracking(vector<int>& nums, int startIndex, vector<bool>& used) { 
        result.push_back(path); 
        unordered_set<int> uset; 
        for (int i = startIndex; i < nums.size(); i++) { 
            if (uset.find(nums[i]) != uset.end()) { 
                continue; 
            } 
            uset.insert(nums[i]); 
            path.push_back(nums[i]); 
            backtracking(nums, i + 1, used); 
            path.pop_back(); 
        } 
    } 
 
public: 
    vector<vector<int>> subsetsWithDup(vector<int>& nums) { 
        result.clear(); 
        path.clear(); 
        vector<bool> used(nums.size(), false); 
        sort(nums.begin(), nums.end()); // 去重需要排序 
        backtracking(nums, 0, used); 
        return result; 
    } 
}; 

補充

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

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

代碼如下：

class Solution { 
private: 
    vector<vector<int>> result; 
    vector<int> path; 
    void backtracking(vector<int>& nums, int startIndex) { 
        result.push_back(path); 
        for (int i = startIndex; i < nums.size(); i++) { 
            // 而我們要對同一樹層使用過的元素進行跳過 
            if (i > startIndex && nums[i] == nums[i - 1] ) { // 注意這里使用i > startIndex 
                continue; 
            } 
            path.push_back(nums[i]); 
            backtracking(nums, i + 1); 
            path.pop_back(); 
        } 
    } 
 
public: 
    vector<vector<int>> subsetsWithDup(vector<int>& nums) { 
        result.clear(); 
        path.clear(); 
        sort(nums.begin(), nums.end()); // 去重需要排序 
        backtracking(nums, 0); 
        return result; 
    } 
}; 

總結

其實這道題目的知識點，我們之前都講過了，如果之前講過的子集問題和去重問題都掌握的好，這道題目應該分分鐘AC。

當然本題去重的邏輯，也可以這么寫

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

其他語言版本

Java

class Solution { 
   List<List<Integer>> result = new ArrayList<>();// 存放符合條件結果的集合 
   LinkedList<Integer> path = new LinkedList<>();// 用來存放符合條件結果 
   boolean[] used; 
    public List<List<Integer>> subsetsWithDup(int[] nums) { 
        if (nums.length == 0){ 
            result.add(path); 
            return result; 
        } 
        Arrays.sort(nums); 
        used = new boolean[nums.length]; 
        subsetsWithDupHelper(nums, 0); 
        return result; 
    } 
 
    private void subsetsWithDupHelper(int[] nums, int startIndex){ 
        result.add(new ArrayList<>(path)); 
        if (startIndex >= nums.length){ 
            return; 
        } 
        for (int i = startIndex; i < nums.length; i++){ 
            if (i > 0 && nums[i] == nums[i - 1] && !used[i - 1]){ 
                continue; 
            } 
            path.add(nums[i]); 
            used[i] = true; 
            subsetsWithDupHelper(nums, i + 1); 
            path.removeLast(); 
            used[i] = false; 
        } 
    } 
} 

Python

class Solution: 
    def subsetsWithDup(self, nums: List[int]) -> List[List[int]]: 
        res = []  #存放符合條件結果的集合 
        path = []  #用來存放符合條件結果 
        def backtrack(nums,startIndex): 
            res.append(path[:]) 
            for i in range(startIndex,len(nums)): 
                if i > startIndex and nums[i] == nums[i - 1]:  #我們要對同一樹層使用過的元素進行跳過 
                    continue 
                path.append(nums[i]) 
                backtrack(nums,i+1)  #遞歸 
                path.pop()  #回溯 
        nums = sorted(nums)  #去重需要排序 
        backtrack(nums,0) 
        return res 

Go

var res[][]int 
func subsetsWithDup(nums []int)[][]int { 
 res=make([][]int,0) 
  sort.Ints(nums) 
 dfs([]int{},nums,0) 
 return res 
} 
func dfs(temp, num []int, start int)  { 
 tmp:=make([]int,len(temp)) 
 copy(tmp,temp) 
 
 res=append(res,tmp) 
 for i:=start;i<len(num);i++{ 
  if i>start&&num[i]==num[i-1]{ 
   continue 
  } 
  temp=append(temp,num[i]) 
  dfs(temp,num,i+1) 
  temp=temp[:len(temp)-1] 
 } 
} 

Javascript

var subsetsWithDup = function(nums) { 
    let result = [] 
    let path = [] 
    let sortNums = nums.sort((a, b) => { 
        return a - b 
    }) 
    function backtracing(startIndex, sortNums) { 
        result.push(path.slice(0)) 
        if(startIndex > nums.length - 1) { 
            return 
        } 
        for(let i = startIndex; i < nums.length; i++) { 
            if(i > startIndex && nums[i] === nums[i - 1]) { 
                continue 
            } 
            path.push(nums[i]) 
            backtracing(i + 1, sortNums) 
            path.pop() 
        } 
    } 
    backtracing(0, sortNums) 
    return result 
};