本文共 1930 字，大约阅读时间需要 6 分钟。
思路：
由于这道题增加了冗余的属性，所以如果用Subset 1中的暴力递归进行求解的话，会浪费很多时间在扫描判断是否有重复值上。因此，类似于全排列的那个题，想到了在之前的基础上添加一个元素即可形成全新的子集的思路。
用一个vector<vector<vector<int>>> newadd变量来记录：每增加一个元素，就增加的子集。
举例：
比如1,2,2这三个元素。
首先newadd中加入一个空集。当1加入之后，增加了{1}。第一个2加入后增加了{2}和{1,2}。第二个2加入后，增加了{2,2}和{1,2,3}。
规律就是，先对输入的vector<int>进行排序，得到一个上升的序列。当一个元素不等于和他相邻的前一个元素时，遍历之前所有的结果集，加上这个元素，作为增加这个元素就增加的子集。如果这个元素和他之前的那个元素重复，则遍历他之前的那个元素对应的结果集，加上这个元素，作为增加这个元素就增加的子集。
在上例中，1之前没有重复元素，遍历之前所有的结果集，只有一个空集，则新增{1}。第一个2需要遍历空集和{1}，第2个2需要遍历{2}和{1,2}。
vector> subsetsWithDup(vector & nums) { vector >> newadd; vector > zero;//0个元素，相当于新增空集 newadd.push_back(zero); int m = nums.size(); if (m==0){ return zero; } vector > result; //要排序 sort(nums.begin(), nums.end()); for (int i = 1; i <= m;i++){ if (i==1 || nums[i-1]!=nums[i-2]){ //如果是nums的第一个元素或这个元素与其前一个不相同 //需要全部遍历之前的newadd元素，并新增 vector > mynewadd; for (int j = 0; j < i;j++){ int len = newadd[j].size();//第j个元素新增的子集数 if (len==0){ vector everyelement; everyelement.push_back(nums[i-1]); mynewadd.push_back(everyelement); continue; } for (int k = 0; k < len;k++){//依次取出第j个元素的新增子集 vector everyelement = newadd[j][k]; everyelement.push_back(nums[i-1]); mynewadd.push_back(everyelement); } } newadd.push_back(mynewadd); } else if(nums[i-1]==nums[i-2]){ //如果和前一个元素重复 //只在前一个元素新增集上新增 vector > mynewadd; int len = newadd[i - 1].size(); for (int k = 0; k < len;k++){ vector everyelement = newadd[i-1][k]; everyelement.push_back(nums[i-1]); mynewadd.push_back(everyelement); } newadd.push_back(mynewadd); } } //再循环拿出每个新增，整个进一个结果集中返回 for (int i = 0; i <= m;i++){ for (int j = 0; j < newadd[i].size();j++){ /*for (vector ::iterator it = newadd[i][j].begin(); it != newadd[i][j].end();it++){ cout << *it << " "; } cout << endl;*/ result.push_back(newadd[i][j]); } } vector tempzero; result.push_back(tempzero); return result;}
转载地址：http://kbdii.baihongyu.com/