Java grouping algorithm

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).

The test scenarios are below

groupSumClump(0, {2, 4, 8}, 10) → true true OK      
groupSumClump(0, {1, 2, 4, 8, 1}, 14) → true true OK      
groupSumClump(0, {2, 4, 4, 8}, 14) → false false OK      
groupSumClump(0, {8, 2, 2, 1}, 9) → true false X   --->Failing   
groupSumClump(0, {8, 2, 2, 1}, 11) → false false OK      
groupSumClump(0, {1}, 1) → true false X      --->Failing
groupSumClump(0, {9}, 1) → false false OK      
other tests  OK      

Snippet is as below

private int sum(final Integer start, final Collection<Integer> list) {
        int sum = start;

        for (final int i : list) {
            sum += i;
        }

        return sum;
}

   public boolean groupSumClump(final int start, final int[] nums, final int target) {       
        for (int i = 0; i < nums.length-1; i++) {
          if(nums[i] == nums[i+1]){//group selected logic
            int sum = nums[i] + nums[i+1];//is this Ok ?
            nums[i] =sum;
            nums[i+1]=0;
          }el开发者_开发知识库se{
          //how to handle the logic for group not selected.               
          }
        }

        final List<Integer> fixed = new ArrayList();
        final List<Integer> candidates = new ArrayList();

        // fills candidates and fixed
        for (int i = 0; i < nums.length; i++) {
            final int cand = nums[i];

            if (cand == 1 && i > 0) {
                final int prev = nums[i - 1];                    
            }else if (cand < target) {
                candidates.add(cand);
            }
        }

        // compute the sum of fixed
        final int sumFixed = sum(0, fixed);

        // if the sum of fixed is equals to target we don't need to do 
        //anything because we already know we need to return true.
        if (sumFixed == target) {
            return true; 
        }            
        if (sumFixed <= target && !candidates.isEmpty()) {
         final Set<Set<Integer>> powerSets = powerSet(new HashSet(candidates));               
            for (final Set<Integer> set : powerSets) {
                if (sumFixed + sum(0, set) == target) {
                    return true; 
                }
            }
        }

        return false;        
}      

 public <T> Set<Set<T>> powerSet(Set<T> originalSet) {       
      Set<Set<T>> sets = new HashSet<Set<T>>();
      if(originalSet.isEmpty()) {
        sets.add(new HashSet<T>());
        return sets;
      }
List<T> list = new ArrayList<T>(originalSet);
T head = list.get(0);
Set<T> rest = new HashSet<T>(list.subList(1, list.size())); 
for (Set<T> set : powerSet(rest)) {
    Set<T> newSet = new HashSet<T>();
    newSet.add(head);
    newSet.addAll(set);
    sets.add(newSet);
    sets.add(set);
}       
return sets;
}  

could you let me whats the problem with the code and why is it failing for test scenarios as mentioned.

i want to know what is the logic for group not selected?

Here is the full solution which passes all your test cases.

Please edit yourself to make it fit to your APIs ^_^

public static void main(String[] args) {
    int nums [] = new int[]{2, 4, 8};
    int target = 10;
    int nums_another [] = grouped (nums);
    System.out.println(viable(0, nums_another, 0, target));
}

private static int [] grouped (int nums []) {
    int nums_another[] = new int [nums.length];
    int i = 0;
    int j = 0;
    i++;
    int c = 1;
    while (i < nums.length){
        if (nums[i] == nums[i-1]) { // count identical numbers
            c++;
        }
        else { // not identical, store sum of previous identical numbers (possibly only 1 number)
            if (nums[i-1] != 0) {
                nums_another[j] = nums[i-1] * c;
                j++;
            }
            c = 1;
        }
        i++;
    }
    if (nums[i-1] != 0) { // store last
        nums_another [j] = nums[i-1] * c; 
    }
    return nums_another;
}

/* partial_sum + sub array of "array from start to 0's" -> target */
private static boolean viable (int partial_sum, int array[], int start, int target) {
    if (partial_sum == target) {
        return true;
    }
    else if (start >= array.length || array[start] == 0) {
        return false;
    }
    else { // Key step
        return viable (partial_sum + array[start], array, start + 1, target)
            || viable (partial_sum,                array, start + 1, target);
    }
}

Key step:

return whether target is viable through sub array, test both cases start is included or not.

One helpful first step would be to replace the array with a LinkedMultiSet. Not a standard runtime collection but easy enough to imagine, find an implementation, or make.