3 replies to this topic

[mamba_namba]

can someone please help me on this practice problem:

Given an array of ints, is it possible to choose a group of some of the ints, such that the group sums to the given target, with this additional constraint: if there are numbers in the array that are adjacent and the identical value, they must either all be chosen, or none of them chosen. For example, with the array {1, 2, 2, 2, 5, 2}, either all three 2's in the middle must be chosen or not, all as a group. (one loop can be used to find the extent of the identical values).

groupSumClump(0, {2, 4, 8}, 10) → true
groupSumClump(0, {1, 2, 4, 8, 1}, 14) → true
groupSumClump(0, {2, 4, 4, 8}, 14) → false

----
its from this site ww.javabat.com/prob?id=Recur2.groupSumClump
----

this is what i came up with but it doesn't work, how can i fix it?:

public boolean groupSumClump(int start, int[] nums, int target) {
if(start>=nums.length){
return target==0;
}

//if identical numbers adjacent exist
if(start!=0 && nums[start]==nums[start-1]){
int count=2;
int i=start+1;
while(i<nums.length && nums[start]==nums[i]){
count++;
i++;
}
//choose all adjacent identical
if(groupSumClump(i, nums, target-((count-1)*nums[start]))) return true;
//choose none
if(groupSumClump(i, nums, target)) return true;

return false;
} else {

//choose
if(groupSumClump(start+1, nums, target-nums[start])) return true;

//dont choose
if(groupSumClump(start+1, nums, target)) return true;

return false;
}
}

[mamba_namba]

you can just ignore my solution and start from scratch if mine is way off

[Coreq]

public boolean groupSumClump(int start, int[] nums, int target) {
if(start>=nums.length){
return target==0;}

if(start!=0 ){ //removed uneeded and statement
int count=0;//I chanced these two values
int i=start;
while(i<nums.length && nums[start]==nums[i]){
count++;
i++;
}
//choose all adjacent identical--i took off the (-1) from count
if(groupSumClump(i, nums, target-((count)*nums[start]))) return true;
//choose none
if(groupSumClump(i, nums, target)) return true;
return false;}

else {

//choose
if(groupSumClump(start+1, nums, target-nums[start])) return true;

//dont choose
if(groupSumClump(start+1, nums, target)) return true;

return false;}
}

Thanks for the start on the program

Edited by WingedPanther, 24 February 2009 - 08:35 AM.
add code tags (the # button)