To remove duplicate combination in DON code...here is the modified code:-
Given an array A[n], start by sorting the array.
Then do something like this:
int result[n];
int size=0;
int prev=-1; // added
void findSubset(int sum, int position=0)
{
if (sum == 0) output(result, size);
for(int i = position; i < n; ++i)
{
if (A[i] > sum) break;
if(prev!=A[i]) // added
{
result[size++] = A[i];
findSubset(sum-A[i], i+1);
prev=A[i]; // added
--size;
}
}
}
Call it like this: findSubset(4);
On Sat, Jan 7, 2012 at 10:25 PM, atul anand <[email protected]> wrote:
> @Don : your algorithm will works but it will print lots of duplicate
> combination.
>
>
>
>
> On Sat, Jan 7, 2012 at 10:00 PM, atul anand <[email protected]>wrote:
>
>> @Don : what would be the complexity of your alogithm??
>>
>>
>> On Sat, Jan 7, 2012 at 2:01 AM, Don <[email protected]> wrote:
>>
>>> Given an array A[n], start by sorting the array.
>>> Then do something like this:
>>>
>>> int result[n];
>>> int size=0;
>>>
>>> void findSubset(int sum, int position=0)
>>> {
>>> if (sum == 0) output(result, size);
>>> for(int i = position; i < n; ++i)
>>> {
>>> if (A[i] > sum) break;
>>> result[size++] = A[i];
>>> findSubset(sum-A[i], i+1);
>>> --size;
>>> }
>>> }
>>>
>>> Call it like this: findSubset(4);
>>>
>>> Don
>>>
>>> On Jan 3, 5:26 am, atul anand <[email protected]> wrote:
>>> > There is integer array like {1,2,4,5,6,1,2,4,3,5,7,2,1}. I want to
>>> find the
>>> > possible combination which will sum to 4.
>>> > input : {1,2,4,5,6,1,2,4,3,5,7,2,1}
>>> > output : {1,1,2}, {2,2}, {3,1}, {1,2,1}{4}...etc which make the sum as
>>> 4
>>> >
>>> > any approach better than O(n^2) ???
>>>
>>> --
>>> You received this message because you are subscribed to the Google
>>> Groups "Algorithm Geeks" group.
>>> To post to this group, send email to [email protected].
>>> To unsubscribe from this group, send email to
>>> [email protected].
>>> For more options, visit this group at
>>> http://groups.google.com/group/algogeeks?hl=en.
>>>
>>>
>>
>
--
You received this message because you are subscribed to the Google Groups
"Algorithm Geeks" group.
To post to this group, send email to [email protected].
To unsubscribe from this group, send email to
[email protected].
For more options, visit this group at
http://groups.google.com/group/algogeeks?hl=en.
