Sum it up problem

#1

How to remove Duplicates in this problem?
Also checkout this code and explain the commented line for checking duplicates!

#2

7
10 1 2 7 6 1 5
8
sorted form
1 1 2 5 6 7 10
CASE 1 : so u first make all the combination adding to 8
using the first one ( 1 2 5) , ( 1 7 ) (1 1 6 )
CASE 2 : then when we move to the next one we would get the same combination like
including the (1 2 5 ), (1 7 )
so in order to prevent the duplicate cases from occuring we would skip the 2nd element
using the

  if (k and a[k] == a[k - 1] and k > i) // Explain this line!!
            continue;

in this condition we check if k > i means we have already checked for first position like in case 1
then when we move to k = 1
we check if a[k] == a[k-1] which is true for k = 1 since we encounter 1 == 1
so we automatically skip making combination and move for k =2

I hope u will understand it.

1 Like
#3

Is there any other approach to check Duplicates?

#4

this is the most frequently used approach else
mantaining a set can help as it removes duplicate but u may encounter tle ( i havent tried that)

    void sum(vector<int>& A , int pos , int target  , vector<int> temp){
        if(target < 0) return;
        else if(target == 0){
            ans.push_back(temp);
            return;
        }
        for(int i = pos ; i < A.size() ; i++){
            if(i > pos and A[i] == A[i-1]) continue;
            temp.push_back(A[i]);
            sum(A, i+1, target-A[i] , temp);
            temp.pop_back();
        }
    }
  
    vector<vector<int>> combinationSum2(vector<int>& A, int target) {
  
              
        vector<int> temp;
        sort(A.begin() , A.end());
        sum(A, 0 , target , temp);
//print ans
        return ans;
  
    }

cleaner code for the approach discussed

u could read the first comment for this post


to understand better