[C++] A concise iterative solution.


  • 0
    J

    It doesn't keep track of the combination sum, because we can alter the target number at any time. And it can handle the duplicates easily by comparing the adjacent numbers.

    class Solution {
    public:
        vector<vector<int>> combinationSum2(vector<int> &num, int target) {
            vector<int> numbers = num;
            sort(numbers.begin(), numbers.end());
    
            vector<vector<int>> result;
            vector<int> indices;  // store the indices of the numbers of a combination in non-descending order
            int i = 0;
            while (i < numbers.size()) {
                if (target == numbers[i]) {
                    vector<int> subset;
                    subset.reserve(indices.size() + 1);  // avoid memory reallocations
                    for (int j : indices) subset.push_back(numbers[j]);
                    subset.push_back(target);
                    result.push_back(move(subset));  // move instead of copy
                }
                // Note: numbers.back() is the maximum
                if (target <= numbers[i] ||
                        (target > numbers[i] && i == numbers.size() - 1) ||
                        (target > numbers.back() * (numbers.size() - i))) {
                    if (indices.empty()) return result;
                    // pop the last added number and update the target number
                    i = indices.back() + 1;
                    target += numbers[i-1];
                    indices.pop_back();
                    // avoid duplicates
                    while (i >= numbers.size() || numbers[i-1] == numbers[i]) {
                        if (i >= numbers.size()) {
                            if (indices.empty()) return result;
                            i = indices.back() + 1;
                            target += numbers[i-1];
                            indices.pop_back();
                        } else {
                            i++;  // ignore the same numbers
                        }
                    }
                } else {
                    target -= numbers[i];
                    indices.push_back(i);
                    i++;
                }
            }
            return result;
        }
    };

Log in to reply
 

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