leetcode:


Given a collection of integers that might contain duplicates, S, return all possible subsets.
Note:
  • Elements in a subset must be in non-descending order.
  • The solution set must not contain duplicate subsets.

  • For example, If S =  [1,2,2] , a solution is:
    [
      [2],
      [1],
      [1,2,2],
      [2,2],
      [1,2],
      []
    ]
    タイトルアドレス:https://oj.leetcode.com/problems/subsets-ii/
    問題解決の考え方:
    Subsetsの問題に比べて、この問題の違いは与えられた数の中に重複する可能性があることです.これにより,以前の解法に従えば,結果セットに同じ集合が現れる可能性がある.
    Subsetsの問題の解法は,1つの要素を追加するごとに,その層の集合=前の層の集合+前の層の各集合の後に新しく追加された要素を加えることである.
    変更すると、重複する場合は要素を追加するたびに、そのレイヤのセット=前のレイヤに新しく追加されたセット+前のレイヤの各セットの後に新しく追加された要素を追加できます.
    コード:
    class Solution {
    public:
        vector > subsetsWithDup(vector &S) {
            vector > ret(1);
            sort(S.begin(),S.end());
            
    		int num=0;
            for(int i=0;i=1&&S[i]==S[i-1]) j=len-num;
                num=0;
                for(;j tmp=ret[j];
                    tmp.push_back(S[i]);
                    ret.push_back(tmp);
    				num++;
                }
            }
            
            return ret;
        }
    };