php网站用的是什么语言写的,企业网站系统功能分析与设计,佛山网站关键词优化公司,互联网域名是什么题目 给你一个整数数组 nums #xff0c;其中可能包含重复元素#xff0c;请你返回该数组所有可能的子集#xff08;幂集#xff09;。 解集 不能 包含重复的子集。返回的解集中#xff0c;子集可以按 任意顺序 排列。 示例 1#xff1a; 输入#xff1a;nums [1,2,2] …题目 给你一个整数数组 nums 其中可能包含重复元素请你返回该数组所有可能的子集幂集。 解集 不能 包含重复的子集。返回的解集中子集可以按 任意顺序 排列。 示例 1 输入nums [1,2,2] 输出[[],[1],[1,2],[1,2,2],[2],[2,2]] 示例 2 输入nums [0] 输出[[],[0]] 分析
子集和组合类问题需要用start保证下一次只能选取后面的元素. 但是数据中有重复,需要进行排序和减枝操作. start为了防止顺序不同的相同集合,start1为了避免重复选择同一数值. 排序为了把相同的数合在一起,减枝为了防止重复选择. 算法框架:
选择列表排序
路径列表
路径
void backtrack(选择列表) {if 路径 合格:路径列表.add(路径)// return 因为子集还能生长if 提前终止:returnfor 选择 in 选择列表[start:]:if 选择 start 选择列表[选择]选择列表[选择-1]:continue //与前一个相同的树枝剪掉路径.add(选择)backtrack(选择列表,选择1)路径.pop(选择) //重新进行下一个选择
}C代码
class Solution {
private:vectorint _trace;vectorvectorint _results;void backtrack(const vectorint nums, const int start){_results.push_back(_trace);for(int istart;inums.size();i){if(istart nums[i]nums[i-1])continue;//减枝_trace.push_back(nums[i]);backtrack(nums, i1);_trace.pop_back();}}
public:vectorvectorint subsetsWithDup(vectorint nums) {sort(nums.begin(),nums.end(),[](int a,int b){return ab;});backtrack(nums,0);return _results;}
};
