groupsumClump Problem
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 mus开发者_StackOverflow社区t 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.
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);
}
}
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;
}
精彩评论