40. 组合总和 II

class Solution {
public:
    vector<vector<int>> combinationSum2(vector<int>& candidates, int target) {
        vector<vector<pair<int, vector<int>>>> dp;

        for (int i = 0; i < candidates.size(); i++)
        {
            vector<pair<int, vector<int>>> tmp;

            int cur = candidates[i];

            if (i > 0)
            {
                vector<pair<int, vector<int>>> & pre = dp[i - 1];
                for (int j = 0; j < pre.size(); j++)
                {
                    pair<int, vector<int>> & p = pre[j];
                    int n = p.first;
                    vector<int> & v = p.second;
                    if (n + cur <= target)
                    {
                        vector<int> vv = v;
                        vv.push_back(cur);
                        tmp.push_back(make_pair(n + cur, vv));
                    }
                    tmp.push_back(p);
                }
            }

            if (cur <= target)
            {
                vector<int> vv;
                vv.push_back(cur);
                tmp.push_back(make_pair(cur, vv));
            }

            dp.push_back(tmp);
        }

        set<vector<int>> tmp;

        vector<pair<int, vector<int>>> & v = dp[dp.size() - 1];
        for (int i = 0; i < v.size(); i++)
        {
            if (v[i].first == target)
            {
                sort(v[i].second.begin(), v[i].second.end());
                tmp.insert(v[i].second);
            }
        }

        vector<vector<int>> ret;
        for (auto i : tmp)
        {
            ret.push_back(i);
        }

        return ret;
    }
};