My concise and fast solution. 20 ms. C++


  • 2
    D

    The idea is absolutely similar like and Combination Sum part 1 + one line :

    if (i && nums[i] == nums[i - 1] && index < i) continue;
    

    I added this line to discard duplicates in result

    Code:

    class Solution {
        vector <int> path;
        vector < vector <int> > res;
    public:
        vector<vector<int> > combinationSum2(vector<int> &num, int target) {
            sort(num.begin(), num.end());
            gen(0, target, num);
            return res;
        }
        void gen(int index, int sum, vector <int> &nums) {
            if (sum == 0) {
                res.push_back(path);
                return;
            }
            
            for (int i = index; i < nums.size(); i++) {
                if (sum - nums[i] < 0) return;
                if (i && nums[i] == nums[i - 1] && index < i) continue;
                path.push_back(nums[i]);
                gen(i + 1, sum - nums[i], nums);
                path.pop_back();
            }
        }
    };

  • 0
    H

    Nice solution .

    if (sum - nums[i] < 0) return;
    if (i && nums[i] == nums[i - 1] && index < i) continue;

    two most important line


Log in to reply
 

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