由于int数组，是否有可能选择一个组的一些整数，例如，该集团款项给定的目标，这个额外的约束：如果有数组中是相邻的相同的数字值，必须将其所有的选择，或者他们没有选择。例如，与阵列{1，2，2，2，5,2}，或者所有三个2的中间必须选择与否，各为一组。 （一个环可以被用来找到相同值的程度）。

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

片断如下

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;
          }else{
          //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;
}  

你能不能让我什么问题与code和为什么它失败的测试场景中提到。

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.

请自行修改，使之适合你的API的^ _ ^

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);
    }
}

关键步骤：

返回是否目标是可行的，通过子阵，测试这两种情况下启动包括与否。

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