[C++]Using Map with 6ms


  • 0
    F
    class Solution {
    private:
        vector<pair<int, int>> list;
        vector<int> sol;
        vector<vector<int>> res;
        void backtrack(int cur) {
            for (int i = cur; i < list.size(); i++) {
                if (list[i].second > 0) {
                    sol.push_back(list[i].first);
                    res.push_back(sol);
                    list[i].second--;
                    backtrack(i);
                    sol.pop_back();
                    list[i].second++;
                }
            }
        }
    public:
        vector<vector<int>> subsetsWithDup(vector<int>& nums) {
            map<int, int> count;
            for (int i = 0; i < nums.size(); i++)
                count[nums[i]]++;
            for (auto x: count)
                list.push_back(make_pair(x.first, x.second));
            res.push_back(vector<int>(0));
            backtrack(0);
            return res;
        }
    };
    

    using map to count the number of a value in the array. So you don't have to compare list[i] with list[i-1] since they are different in the vector<pair<int, int>> list. Maybe a tree would help understand:
    given[1, 2, 2, 3]

               [  empty  ]   <---add[]
            /       |    \
          1         2     3    <---add[1], [2], [3]
        /   \      /  \
      2      3    2    3   <---add[1, 2], [1, 3], [2, 2], [2, 3]
     /  \         |
    2    3        3   <---add[1, 2, 2], [1, 2, 3], [2, 2, 3]
    |
    3   <---add[1, 2, 2, 3]
    

    The output sequence is not layer-based, but depth-based. My poor English...


Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.