My concise 14ms C++ solution


  • 5
    P
    class Solution {
    public:
        vector<vector<int> > combinationSum2(vector<int> &num, int target) {
            vector<vector<int> > result;
            sort(num.begin(), num.end());
            combHelper(num, 0, num.size(), target, vector<int>(), result);
            return result;
        }
        
        void combHelper(vector<int>& a, int start, int n, int target, 
        vector<int> cur_vec, vector<vector<int> >& result) {
            
            if (target == 0) {
                result.push_back(cur_vec);
                return;
            }
            int i = start;
            while(i < n  && target-a[i] >= 0) {
                // NOTE : this condition helps neglecting making identical sets
                //  this is the catch of this question
                if (i == start || a[i] != a[i-1]) {
                    cur_vec.push_back(a[i]);
                    combHelper(a, i+1, n, target-a[i], cur_vec, result);
                    cur_vec.pop_back();
                }
                i++;
            }
        }
    };

  • 1
    A

    mark, many years pass by, I still misuse dfs every time......


  • 0
    T

    isn't this solution going to have a problem with input like [1, 1] 2 ? my understanding is that multiple elements of equal value can be included in the combo. but the line "a[i] != a[i-1] " in the above solution precludes this answer.


  • 0
    W

    @teddyyyy Good observation but I think that's not a problem. Given the input [1, 1] and the target is 2. The [1,1] will return simplly handled by the if statement i == start condition in another level of recursion


Log in to reply
 

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