Recursion sum numbers *with rule* - Recursion only

Question

So the exercise is:

Using recursion only (no loops)

Find if there is sub ground of numbers that are equal to the given number in an array and follow the rule.

Let's say I have this array, I give the function a number for sum and it must adhere to this rule: you cannot repeat the same number, and you can't sum 3 numbers in a row (can't do i+1 and i+2)

int[] a = {5,4,2,1,3};

So in this case: num 8 = true (4+3+1) ( 5+3) num 11 = false (4+5+2 are 3 but are three in a row) (5+2+1+3 also three in a row)

My attempt is:

public static boolean sumRule(int[] a , int num){
        if (num == 0){
            return true;
        } else {

    return sumRule(a,num,0,a.length);
        }
}

private static boolean sumRule(int[] a, int num, int low,int high){
    if(low >= high || low < 0){
        return false;
    }

    if (a[low] == -1){
        return false;
    }

    if(a[low] == num || num-a[low] == 0 ){
        return true;
    }

    int temp = a[low];
    a[low] = -1;

    return  sumRule(a,num,low,high) || sumRule(a,num-temp,low+3,high) || sumRule(a,num-temp,low+1,high) ;

}

But when I send 11 to this, it still returns true, anyone has an idea what am i missing here?

Thanks,

Answer 1

public static boolean isSum(int[] a, int index, int sum){

if(sum==0){
    return true;
}

if(index>=a.length-1 || sum<0){
    return false;
}

    return isSum(a,index+3,sum-a[index]-a[index+1]) || isSum(a,index+2,sum-a[index]) || isSum(a,index+1,sum);
}


public static boolean isSum(int[] a, int sum){

    return isSum(a,0,sum);

}

Answer 2

First thing you can add is a check to see not 3 numbers in a row being added. Also replacing a number in the array with -1 would have unintended side effects within recursive calls. Below is something I have. You can ignore the index param I have used to see the values used.

Explanation: The recursive sumRule method divides the problem into two parts:

• First part takes the value of current index and adds with the sum of values starting from next index.
• Second part assumes, current value can’t be taken for the sum. It only checks if there is a sum within the subset starting from next value of the array.

In the method, lastIndex is keeping track of the index of last value picked up for the sum. So, in the first call the value is 0, 1 in second and so on.

(start - lastIndex <= 1 ? consecutive + 1 : 1) is to check whether value of consecutive should be increased or not. consecutive = 1 means, current value is added to the sum.

  public static boolean sumRule(int[] a, int num) {
    if (num == 0) {
      return true;
    } else {
      return sumRule(a, num, 0, 0, 0, 0, "");
    }
  }

  public static boolean sumRule(final int[] a, int num, int sum, int start, int consecutive, int lastIndex,
      String index) {
    if (consecutive == 3) {
      return false;
    }

    if (sum == num) {
      System.out.println(index);
      return true;
    }

    if (start >= a.length) {
      return false;
    }

    return sumRule(a, num, sum + a[start], start + 1, (start - lastIndex <= 1 ? consecutive + 1 : 1), start,
        index + ", " + start) || sumRule(a, num, sum, start + 1, consecutive, lastIndex, index);
  }

Answer 3

I have the full code answer below, and here's the explanation:

Essentially you need to break this problem down to a recurrence. What that means is, you look at the choice at each step (i.e. whether to use a number or not in the sum) and recursively calculate both options.

The base case: If num == 0 then we know it's true. But if num != 0 and the array has length 0, then we know it's false

Recursive case: We check if the first number in the array is less than or equal to num. If not, then we can't use it. So we do a recursive call with all the same parameters except the array is now the original array minus the first number

If we CAN use the number (i.e. a[0] <= num) then the true answer might use this or it may not use it. We make a recursive call for each case, and return true if either of the recursive calls return true.

The consecutive number rule: This is easy to enforce. We add a parameter called 'left' which tells us the number of elements we can consecutively take from the beginning of the array. To start with, left is 2 because at most we can take 2 consecutive numbers. Then in the cases where we DO use the first number in the array in our sum, we decrement left. If we don't use the first number in the array, we reset left to 2. In the cases where left becomes 0, we have no choice but to skip the current number at the top of the array.

class Main {
  public static void main(String[] args) {
    int[] a = new int[] {5,4,2,1,3};
    System.out.println(sumRule(a, 8));
    System.out.println(sumRule(a, 11));
  }

  public static boolean sumRule(int[] a , int num){
    if (num == 0){
        return true;
    } else {
      return sumRule(a,num,2);
    }
  }

  private static boolean sumRule(int[] a, int num, int left){
      if (num == 0) {
        return true;
      }

      if (a.length == 0) {
        return false;
      }

      int[] a_new = new int[a.length-1];
      for (int i = 1; i < a.length; i++) a_new[i-1] = a[i];

      if (left == 0) {
        return sumRule(a_new, num, 2);
      }

      boolean using_a0 = false;
      if (a[0] <= num) {
        using_a0 = sumRule(a_new, num-a[0], left-1);
      }

      boolean not_using_a0 = sumRule(a_new, num, 2);

      return (not_using_a0 || using_a0);
  }
}

Edit - A variation on the code above without copying the array:

class Main {
  public static void main(String[] args) {
    int[] a = new int[] {5,4,2,1,3};
    System.out.println(sumRule(a, 8));
    System.out.println(sumRule(a, 11));
  }

  public static boolean sumRule(int[] a , int num){
    if (num == 0){
        return true;
    } else {
      return sumRuleNoLoop(a,num,2,0);
    }
  }

  private static boolean sumRuleNoLoop(int[] a, int num, int left, int startIdx){
      if (num == 0) {
        return true;
      }

      if (startIdx >= a.length) {
        return false;
      }

      if (left == 0) {
        return sumRuleNoLoop(a, num, 2, startIdx+1);
      }

      boolean using_a0 = false;
      if (a[startIdx] <= num) {
        using_a0 = sumRuleNoLoop(a, num-a[startIdx], left-1, startIdx+1);
      }

      boolean not_using_a0 = sumRuleNoLoop(a, num, 2, startIdx+1);

      return (not_using_a0 || using_a0);
  }
}

Answer 4

Here is my implementation. It contains comments explaining what the different parts do.

public class RecurSum {
    /**
     * Determines whether 'sum' equals 'target'.
     * 
     * @param arr         - its elements are summed
     * @param sum         - sum of some elements in 'arr'
     * @param target      - required value of 'sum'
     * @param index       - index in 'arr'
     * @param consecutive - number of consecutive indexes summed to ensure don't exceed 3
     * @param start       - starting element in 'arr' which is used for back-tracking
     * 
     * @return "true" if 'sum' equals 'target'
     */
    private static boolean sumRule(int[] arr, int sum, int target, int index, int consecutive, int start) {
        if (sum == target) {
            return true;
        }
        else {
            if (index >= arr.length) {
                // if we have reached last element in 'arr' then back-track and start again
                if (start < arr.length) {
                    return sumRule(arr, 0, target, start + 1, 0, start + 1);
                }
                // we have reached last element in 'arr' and cannot back-track
                return false;
            }
            else {
                consecutive++;
                if (consecutive == 3) {
                    // skip 3rd consecutive element (because of the rule)
                    consecutive = 0;
                    return sumRule(arr, sum, target, index + 2, consecutive, start);
                }
                else {
                    if (sum + arr[index] > target) {
                        // recursive call but don't add current element of 'arr'
                        return sumRule(arr, sum, target, index + 1, 0, start);
                    }
                    // recursive call: add current element of 'arr' to 'sum' and proceed to next element
                    return sumRule(arr, sum + arr[index], target, index + 1, consecutive, start);
                }
            }
        }
    }

    public static void main(String[] args) {
        int[] arr = new int[]{5, 4, 2, 1, 3};

        // initial call to recursive method with target = 11 (eleven)
        System.out.println(sumRule(arr, 0, 11, 0, 0, 0));

        // initial call to recursive method with target = 8
        System.out.println(sumRule(arr, 0, 8, 0, 0, 0));
    }
}