90.md

【中规中矩】90. 子集 II （经典回溯）

解题思路

如果不考虑有重复元素的话，基本就是经典回溯模板题目。基本套路就是定义一个out数组，一个res结果数组，和起点位置start,在backtracking函数里根据条件将out放入res中，主题是从start到数组结尾循环，尝试做选择加入当前元素，递归进入下一层，然后递归回来之后撤销选择pop掉上次选择的元素。如果有重复的话，有两种处理方法。其一：排序后回溯，遇到相邻重复元素跳过。其二：用set保存子集合，自动筛选掉重复，最后转换为C++ vector of vector 或Python list of list即可。

代码

class Solution {
public:
    vector<vector<int>> subsetsWithDup(vector<int>& nums) {
        set<vector<int>> res;
        vector<int> out;
        sort(nums.begin(), nums.end());
        backtracking(nums, 0, out, res);
        return vector<vector<int>>(res.begin(), res.end());
    }
    
    void backtracking(vector<int>& nums, int start, vector<int>& out, set<vector<int>>& res) {
        res.insert(out);
        if (out.size() == nums.size())
            return;
        
        for (int pos = start; pos < nums.size(); pos++) {
            out.push_back(nums[pos]);
            backtracking(nums, pos + 1, out, res);
            out.pop_back();
        }
    }
};

class Solution:
    def subsetsWithDup(self, nums: List[int]) -> List[List[int]]:
        res, out = [], []
        nums.sort()
        self.backtracking(nums, 0, out, res)
        return res

    def backtracking(self, nums, start, out, res) :
        # res.append(out) # Wrong coding
        res.append(copy.deepcopy(out))
        for pos in range(start, len(nums)):
            if pos > start and nums[pos] == nums[pos - 1]:
                continue # skip dup numbers
            out.append(nums[pos])
            self.backtracking(nums, pos + 1, out, res)
            out.pop()
    

点我赞赏作者

github 题解