90. Subsets II

题目链接

https://leetcode.com/problems/subsets-ii/

思路

对于第i个数，要么选和不选，不选就是前i-1个数的结果，选就是在前i-1个数的基础上加上第i个数，如果第i个数和第i-1个数相等，只需要考虑第i-1个数加入过集合的那部分子集。

代码

class Solution {
public:
    vector<vector<int>> subsetsWithDup(vector<int>& nums) {
        vector<vector<int>> ans;
        sort(nums.begin(), nums.end());

        vector<int> t;
        ans.push_back(t);
        int pos = 0, st = 0;
        for (int i = 0; i < nums.size(); ++i) {
            if ( i != 0 && nums[i] == nums[i - 1]) {
                st = pos;
            } else {
                st = 0;
            }
            pos = ans.size();
            int ed = ans.size();
            for (; st < ed; ++st) {
                t = ans[st];
                t.push_back(nums[i]);
                ans.push_back(t);
            }
        }
        return ans;
    }
    
};