CODEWITHSUNDEEP
javaarrays
Anirudh
Anirudh

Reputation: 2326

Determining if there exists a subset in a Array of Integers that sums to a given target value under a couple of conditions

The 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 a value in the array is chosen to be in the group, the value immediately following it in the array must not be chosen.

For eg:-

groupNoAdj(0, {2, 5, 10, 4}, 12) → true

groupNoAdj(0, {2, 5, 10, 4}, 14) → false

groupNoAdj(0, {2, 5, 10, 4}, 7) → false

As you can see in the last case though there exists as subset {2,5} which sums to target value '7' but they are adjacent values and hence can't to chosen together. Also there is another condition that you can't use a local variable.

I came up with the solution below: 

public boolean groupNoAdj(int start, int[] nums, int target) {
    if(start==nums.length)
        return target==0;
    if(start==nums.length-1&&!(target==0))
        return (target-nums[start]==0);


    if(target==0)
       return true;

    if((start<nums.length-1)&&groupNoAdj(start+1, nums, target-nums[start]))
           return groupNoAdj(start+2, nums, target-nums[start]);

   return groupNoAdj(start+1, nums, target);
}

But it's failing in case groupNoAdj(0, {2, 5, 10, 4, 2}, 7) it's returning false when it should actually return true

Can't really spot what's causing it to fail in this case.

Upvotes: 2

Views: 456

Answers (1)

Nir Alfasi
Nir Alfasi

Reputation: 53525

You missed something in your last condition:

public static void main(String[] args) {
    int[] arr1 ={2, 5, 10, 4};
    int[] arr2 = {2, 5, 10, 4};
    System.out.println(groupNoAdj(0, arr1, 12)); // prints true
    System.out.println(groupNoAdj(0, arr2, 7));  // prints false
}

public static boolean groupNoAdj(int start, int[] nums, int target) {

    if(target == 0)
        return true;

    if(start == nums.length)
        return target==0;

    if(start == nums.length-1)
        return target-nums[start] == 0;

    return
            groupNoAdj(start+2, nums, target-nums[start]) || // either pick the "current" item (and skip the "next") 
            groupNoAdj(start+1, nums, target);               // or don't pick it
}

Upvotes: 1

Related Questions