Combination Sum - II

#1

Here is the question:- https://leetcode.com/problems/combination-sum-ii/, and here is the code implemented to solve it:- https://ide.codingblocks.com/s/453803.
Please note few things before proceeding:-
i) when I don’t comment out line 12 then the answer is something diff and also 1 is repeating twice, though it should not and also the sum of ans 1 1 2 is not equal to target 5.
2) When I comment out line 12 then answer is something different and repeat, though I have used set therefore, to store unique combinations, still getting the duplicate vectors.

Please specify what is the mistake.?

#2

hello @Sakshi2004

checck now->

by passing v by reference->

#3

But the set is still storing duplicates, why so? I am getting 2 1 2 and 2 2 1 when I don’t comment out line 13 of sort function, why so? Please explain. And also, how passing v as reference is making a difference, not getting that because we are backtracking and popping out the last element, and checking for next element if it contributes in making the combination.

#4

they are different because order of elements are different.

when u are sorting before inserting then they are in same order 1 2 2 hence set include only one of them.

to resolve this.

dont use sort function iside that if instead sort the candidate in the start itself (before calling ur combination function)
and then all gebrated combinations will automically be in sorted order.

#5

check the comment i mentioned in second code

#6

Got this point, Thanks.

#8

Ya checked your comment, but it is bit not understandable to me, if you could explain with small example, how?

#9

let say the combination generated is 2 1 (when we hit base case ).
now before insering in set , u r sorting so it will be 1 2 .(note we have passed v by reference so this change will happen in original vector)
and then u will return back.
when u return back u will pop back , 2 will be popped out becuase now the vector is (1,2) but it was supposed to be (2,1).
so this is why u r getting weired output.

#10

oh ok, Thanks a lot for clearing the doubt. This is something I was not able to think of. And it means if I sort the vector in beginning only then I could pass it by reference na?

#11

yeah …then u can do that. . . .