C++ Iterative solution which avoids duplicates


  • 0
    D

    We solve this the same way we would solve the subset-sum problem.

    The key observation for avoiding duplicates is that if we are processing the k'th instance of a number, then it can only extend solutions that have (k-1) 1's (for example). So when processing the 3rd instance of a number, we only extend solutions with 2 instances of that number. If we sort the numbers initially, we are guaranteed that if a solution has to include (k-1) instances of a number, then the suffix of the solution must have those numbers. This check can be done in O(1) time because we process the numbers sorted.

    class Solution {
        typedef vector<int> soln_t;
        typedef vector<soln_t> solns_t;
        vector<solns_t> combo;
    
        int getNum(soln_t &soln, int i, int def) {
            if (i < 0 || i >= soln.size()) return def;
            return soln[i];
        }
    
        bool hasExactlyK(soln_t &soln, int n, int k) {
            int idx = soln.size() - 1;
            bool ret = soln.size() >= k && getNum(soln, idx-k, n+1) != n && getNum(soln, idx-k+1, n) == n;
            return ret;
        }
    
    public:
        vector<vector<int>> combinationSum2(vector<int>& candidates, int target) {
            std::sort(candidates.begin(), candidates.end());
            combo.clear();
            combo.resize(target+1);
            combo[0] = solns_t(1);
            // Stores how many instances of a number have been seen so far.
            unordered_map<int, int> seen;
    
            for (int n: candidates) {
                int instances = seen[n]++;
                for (int i = target - n; i >= 0; --i) {
                    for (auto x: combo[i]) {
                        if (hasExactlyK(x, n, instances)) {
                            x.push_back(n);
                            combo[i + n].push_back(x);
                        }
                    }
                }
            }
            return combo[target];
        }
    };
    

Log in to reply
 

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