Problem:
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
Solution:
public boolean groupSumClump(int start, int[] nums, int target) {
altArray(nums);
if (start >= nums.length) return target == 0;
if (groupSumClump(start+1, nums, target-nums[start])) return true;
if (groupSumClump(start+1, nums, target)) return true;
else return false;
}
private void altArray(int[] nums) {
for (int i = 0; i < nums.length; i++) {
if (i > 0 && nums[i] == nums[i-1]) {
nums[i-1] += nums[i];
if (i+1 < nums.length && nums[i] != nums[i+1])
nums[i] = 0;
else if (i == nums.length-1)
nums[i] = 0;
}
}
}
public boolean groupSumClump(int start, int[] nums, int target) {
ReplyDeleteif (start==nums.length) return target==0;
for(int i=start,j=nums[i];i<nums.length-2 && j==nums[i+1];i++){
nums[start]+=nums[i+1];
nums[i+1]=0;
}
if (groupSumClump(start+1, nums, target-nums[start])) return true;
if (groupSumClump(start+1, nums, target)) return true;
return false;
}
public boolean groupSumClump(int start, int[] nums, int target) {
ReplyDeleteif (start >= nums.length) return (target == 0);
if (start<nums.length-1 && nums[start]==nums[start+1])
{
return groupSumClump(start+2, nums, target);
}
if (groupSumClump(start + 1, nums, target)) return true;
if (groupSumClump(start + 1, nums, target - nums[start])) return true;
return false;
}
About the solution above from October 16. Am I missing something or does it not cover the case where all the identical numbers are used? I tested it and it works however from the visible solutions there is no case where all the identical numbers are used.
ReplyDeletepublic boolean groupSumClump(int start, int[] nums, int target) {
ReplyDeleteif(start>=nums.length)return target==0;
int i = nums[start];int x = 0;
while((x+start)<nums.length&&nums[start+x]==i)
x++;
if (groupSumClump(start+x, nums, target-x*i)) return true;
if (groupSumClump(start+x, nums, target)) return true;
return false;
}
About the solution above from October 16.
ReplyDeleteI solved the same way, but to satisfy all the requirements I added one more check, and yet it works, but it depends on what order you put.
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]){
return groupSumClump( start + 2 , nums , target ) ;
}
if ( start < nums.length -1 && nums[start] == nums[start+1]){
return groupSumClump( start + 2 , nums , target - nums[start]-nums[start] ) ;
}
if ( groupSumClump( start + 1 , nums , target - nums[start]) ) return true;
if ( groupSumClump ( start + 1 , nums , target ) ) return true;
return false;
}
altArray breaks down for inputs with more than 2 identical numbers. For example: [8, 2, 2, 1] nominally returns [8, 4, 0, 1], however when tested with [8, 2, 2, 2, 1], [8, 4, 4, 0, 1] is incorrectly returned. It should be [8, 6, 0, 0, 1] instead.
ReplyDeleteHere's a proper solution:
public static void reArrange(int[] nums) {
if(nums.length == 0) return;
int clusterStart = 0;
int clusterNum = nums[clusterStart];
for(int i = 1; i < nums.length; i++) {
if(nums[i] == clusterNum) {
nums[clusterStart] += nums[i];
nums[i] = 0;
} else {
clusterStart = i;
clusterNum = nums[i];
}
}
}
public boolean groupSumClump(int start, int[] nums, int target) {
ReplyDeleteif (start >= nums.length)
{
return target == 0;
}
else
{
int count = start;
int sum = nums[start];
while (count + 1 < nums.length && nums[count] == nums[count + 1])
{
count++;
sum += nums[count];
}
if (count > start)
{
return groupSumClump(count + 1, nums, target - sum)
|| groupSumClump(count + 1, nums, target);
}
else
{
return groupSumClump(start + 1, nums, target - nums[start])
|| groupSumClump(start + 1, nums, target);
}
}
}
private final boolean groupSumClump(int start, int[] nums, int target) {
ReplyDeleteif (start >= nums.length){
return (target == 0);
}
if (start < nums.length - 1 && nums[start] == nums[start + 1]){
return groupSumClump(start + 2, nums, target) ;
}
return groupSumClump(start + 1, nums, target - nums[start])
|| groupSumClump(start + 1, nums, target);
}
let's say you have 3 of the same number in a row, you will skip the first two then get to the third which is dissimilar from the next number, so it will include it when it shouldnt
Deletepublic boolean groupSumClump(int start, int[] nums, int target) {
ReplyDeleteif (start>=nums.length) return (target == 0);
if (start<nums.length-1&&nums[start]==nums[start+1]) {
int len = 2;
for (int i = start+1; i<nums.length-1; i++){
if (nums[i]==nums[i+1]) { len++;}
else { break;}
}
return groupSumClump(start+len, nums, target) || groupSumClump (start+len, nums, target-(nums[start]*len));
}
return groupSumClump(start+1, nums, target) || groupSumClump (start+1, nums, target-nums[start]);
}
public boolean groupSumClump(int start, int[] nums, int target) {
ReplyDeleteif (start >= nums.length)
return target == 0;
int count = 1;
for (int i = start; i < nums.length - 1 && nums[i] == nums[i+1]; i++){
count++;
}
return groupSumClump(start+count, nums, target - count*nums[start]) || groupSumClump(start+count, nums, target);
}
public static boolean groupSumClump(int start, int[] nums, int target) {
ReplyDeleteif (start >= nums.length) return (target==0);
int count=1;
int tracker=start;
while (tracker1)
return groupSumClump(start+count, nums, target-subtot)||groupSumClump(start+count, nums, target);
if (groupSumClump(start+1, nums, target)) return true;
if (groupSumClump(start+1, nums, target-nums[start])) return true;
return false;
}
Deletepublic static boolean groupSumClump(int start, int[] nums, int target) {
if (start >= nums.length) return (target==0);
int count=1;
int tracker=start;
while (tracker1)
return groupSumClump(start+count, nums, target-subtot)||groupSumClump(start+count, nums, target);
if (groupSumClump(start+1, nums, target)) return true;
if (groupSumClump(start+1, nums, target-nums[start])) return true;
return false;
}
reposting after some weird stuff happened with the formatting above.
All your code will fail for sure for this input - (0, {10, 2, 2 5}, 17)
ReplyDeleteBest & simplest solution will be -
public boolean targetSum(int start, int[] nums, int target) {
if (start >= nums.length)
return (target == 0);
if (targetSum(start + 1, nums, target - nums[start]))
return true;
if (targetSum(start + 1, nums, target))
return true;
return false;
}