Link to home
Start Free TrialLog in
Avatar of gudii9
gudii9Flag for United States of America

asked on

groupSumClump challenge

Hi,

 I am working on below challenge

http://codingbat.com/prob/p105136
[/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

I was nt clear on the description and additional constraints .

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.
please advise
SOLUTION
Avatar of zzynx
zzynx
Flag of Belgium image

Link to home
membership
This solution is only available to members.
To access this solution, you must be a member of Experts Exchange.
Start Free Trial
SOLUTION
Link to home
membership
This solution is only available to members.
To access this solution, you must be a member of Experts Exchange.
Start Free Trial
@gudii9
Are you still there?
Avatar of gudii9

ASKER

any pseudo code, design for this?please advise
ASKER CERTIFIED SOLUTION
Link to home
membership
This solution is only available to members.
To access this solution, you must be a member of Experts Exchange.
Start Free Trial
Avatar of gudii9

ASKER

i am still trying to understand backward recursion concept
Avatar of gudii9

ASKER

public boolean groupSumClump(int start, int[] nums, int target) {
    if (start >= nums.length) return target == 0;
 
    int sum = nums[start];
    int count = 1;
[b]    for (int i = start + 1; i < nums.length; i++)[/b]
        if (nums[i] == nums[start]) {
            sum += nums[i];
            count++;
        }
    return groupSumClump(start + count, nums, target - sum)
            || groupSumClump(start + count, nums, target);

Open in new window


in above solution why we need additional for loop here? please advise
in above solution why we need additional for loop here?

that is because the challenge is to handle multiple occurrences of the same number as one number.

with the loop you count the length of sub array with same number. if count == 1 the challenge is same as groupsum challenge.

Sara