90-子集2(回溯算法)

题目

���你一个整数数组 nums ，其中可能包含重复元素，请你返回该数组所有可能的子集（幂集）。

解集 不能 包含重复的子集。返回的解集中，子集可以按 任意顺序 排列。

示例 1：

输入：nums = [1,2,2]

输出：[[],[1],[1,2],[1,2,2],[2],[2,2]]

示例 2：

输入：nums = [0]

输出：[[],[0]]

分析

子集和组合类问题需要用start保证下一次只能选取后面的元素.

但是数据中有重复,需要进行排序和减枝操作.

start为了防止顺序不同的相同集合,start+1为了避免重复选择同一数值.

排序为了把相同的数合在一起,减枝为了防止重复选择.

算法框架:

选择列表排序路径列表路径void backtrack(选择列表) {if 路径 合格:路径列表.add(路径)// return 因为子集还能生长if 提前终止:returnfor 选择 in 选择列表[start:]:if 选择 > start && 选择列表[选择]==选择列表[选择-1]:continue //与前一个相同的树枝剪掉路径.add(选择)backtrack(选择列表,选择+1)路径.pop(选择) //重新进行下一个选择}

C++代码

class Solution {private:    vector _trace;    vector _results;    void backtrack(const vector& nums, const int& start){        _results.push_back(_trace);        for(int i=start;i            if(istart&& nums[i]==nums[i-1])                continue;//减枝            _trace.push_back(nums[i]);            backtrack(nums, i+1);            _trace.pop_back();        }    }public:    vector subsetsWithDup(vector& nums) {        sort(nums.begin(),nums.end(),[](int a,int b){return a