groupsumClump Problem

Question

Im struggling to get the below problem right for a quite a while sometime.

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, {8, 2, 2, 1}, 9) → true      
  groupSumClump(0, {2, 4, 4, 8}, 14) → false

The code is at http://ideone.com/Udk5q

Failing test case scenarios:

 groupSumClump(0, {2, 4, 4, 8}, 14) → false -->NegativeArraySizeException
 groupSumClump(0, {8, 2, 2, 1}, 9) → true false --> X

i have really tried my best to make it work but alas its failing always. Please Need your help SO experts to resolve this problem I will be highly obliged and thankful to you,if you can spare a few minutes to look into my problem as well and help me in acheieving the desired solution.

score 1 · Answer 1 · edited May 23 '17 at 12:04

Method "summate" logic is realy messed up. It should look something like function "f" here: Algorithm to find which numbers from a list of size n sum to another number

Quick and dirty fix for your code:

class Demo {
public static void main(String args[]) {
    Demo.groupSumClump(0, new int[] { 2, 4, 4, 8 }, 14);
    Demo.groupSumClump(0, new int[] {8, 2, 2, 1}, 9);
}

public static void groupSumClump(int start, int[] nums, int target) {
    start = 0;

    nums = adjacents(start, nums);

    for (int a_number = 0; a_number < nums.length; a_number++) {
        System.out.println("Array is " + nums[a_number]);
    }
    summate(nums, 0, 0, target);
    System.out.println(false);
}

public static int[] adjacents(int start, int[] nums) {
    int sum = 0;
    for (int i = 0; i < nums.length - 1; i++) {
        if (nums[i] == nums[i + 1]) {
            sum += nums[i] + nums[i + 1];
            nums[i] = sum;
            nums[i + 1] = 0;
        }
    }
    return nums;
}

static void check(int sum, int target) {
    if (sum == target) {
        System.out.println(true);
        System.exit(0);
    }
}

static void summate(int[] numbers, int index, int sum, int target) {
    check(sum, target);
    if (index == numbers.length) {
        return;
    }
    summate(numbers, index + 1, sum + numbers[index], target);
    check(sum, target);
    summate(numbers, index + 1, sum, target);
    check(sum, target);
}
}

can you please provide the fix to the existing code logic written in java.i want to refine my code without altering it much. — deepakl.2000, May 17 '11 at 09:37
i have to accomplish the summate without recursion technique.please provide without recursion logic for my existing java code logic — deepakl.2000, May 17 '11 at 10:26
Well, you used recursion in your code too. Read http://en.wikipedia.org/wiki/Subset_sum_problem — bigGuy, May 17 '11 at 10:44

score 1 · Answer 2 · answered Sep 24 '21 at 14:01

 public boolean groupSumClump(int start, int[] nums, int target) {
 
      if(start >= nums.length) return target == 0;
  
      if(start < nums.length-1 && nums[start] == nums[start+1]){
         int span = 0;
         for(int i = start; i < nums.length && nums[i] == nums[start]; i++){
             span++;
        
    } if(groupSumClump(start + span, nums, target)) return true;
       return groupSumClump(start + span, nums, target - nums[start] * span);
       
  
    
    } if(groupSumClump(start + 1, nums, target-nums[start])) return true;
      if(groupSumClump(start +1, nums, target)) return true;
      return false;
    }

Your answer could be improved with additional supporting information. Please [edit] to add further details, such as citations or documentation, so that others can confirm that your answer is correct. You can find more information on how to write good answers [in the help center](/help/how-to-answer). — Community, Sep 24 '21 at 15:50

groupsumClump Problem

2 Answers2

Linked