Sum it up . not getting the right approach

#1

is my approach correct?

#2

Hey , you need to approach the question in a different way, i`ll update the code and share the link in a while

#3

See, I`ll tell u how to approach the question

  1. sort the array
  2. create a vector<vector> ans to store the variable no of vector which equals target sum
  3. pass in an empty vector to the helper function
    helper( ans , temp , index : 0 , sum : 0 , target)

now in the helper function

  1. base condition if sum == target
    add current vector to ans
  2. if sum > target ;:: return since this vector would never give u the target
  3. interate over the entire array
    for(int i = index ; i < n ; i++){
    if(i > index and vec[i ] == vec[i-1] ) continue
    temp.push_back(vec[i]) // adding currrent element
    helper( vec, temp , i+1 , sum+ vec[i] , target ) // recursive call
    temp.pop_back(); // remove the last added element

Code :

#4

@chhavibansal can you explain this line
if(i > index and vec[i ] == vec[i-1] ) continue

#5

yes
see we have duplicates values in the i/p array
so we need to take care that we do not form duplicate sets

10 1 2 7 6 1 5
sorted: 1 1 2 5 6 7 10

if we have included a element once, and formed a set once, which gives us the target value,
so we would not want to create another set with the same character

for eg
1 2 5 sums up to 8 (we include 1 which is at index 0 )
then when we are at index 1, if we again take this 1 and 2 5 we would get the target value , but this would give u a duplicate vector

so basically we check if ( i > index and vec[i] == vec[i-1] ) so that we do not include 1 at index 1 .

to understand better try removing this line and check the o/p

1 Like