Clever glimpse needed with this recursion

[Yakg]

Hi, the following program should take two parameters (array[],int number)
and checks if the given number could be returned by summing or subtracting the objects in from the array.
Ex. if number is: 31 and the array {5,22,13,5,7,-4}.
Returns true because 22+13-4=31 .

My code isn't finish I just want to know if I'm doing too much or should I go on with this madness. It should be all recursive no loops.

My idea: I wanted to sort the array first from large to small numbers and then
take the largest and if larger find a negative value and if smaller keep adding.

public class Test2Q1{
    
    public static boolean cover (int [] values, int amount){
    if (values.length>1)
        cover (values,0,1,amount) ;
        return false;
    }
    
    private static boolean cover (int [] values, int i, int j, int amount){ //rearranger
        int key = values[j];
        i = j-1;
        if (i>-1 && values[i] < key){
            values[i+1] = values[i];
            cover (values,i=i-1,j,amount);
        }
        values [i+1] = key;
        if (j<values.length)
        cover (values,i,j++,amount);
        return cover(values,amount,0,0);
    }
    
    private static boolean cover (int [] values,int amount, int i,int neg){ //find negatives
        if ( i<values.length-1){
        if (values[i] >0) 
        cover (values,amount,i+1,neg);
        cover (values,amount,i+1,neg+1);
    }
    return cover (values,amount,neg,0,0);
}
// ----- phase 1. array rearranged and the neg values found. -----.
    
// Start of phase 2.
    private static boolean cover (int [] values,int amount, int neg, int helper, int i){ //checks if == or <
       neg = (values.length)-neg;
       if (helper<amount) 
       helper += values[i];
        if (helper == amount) //base case
        return true;
        //------------------------------ok---!
        if (helper<amount)
        cover (values,amount,neg,helper,i+1); //continue as long as helper is < than the amount.
        //if >
        if (neg != values.length){ //if there are negative values.
            helper+=neg;
            if (helper>amount)
             cover (values,amount,neg-1,helper,i);
             //if <

It's unfinished I know it's long but just a quick look would help.
Your help is much appreciated thanks.

[JosAH]

Hi, the following program should take two parameters (array[],int number)
and checks if the given number could be returned by summing or subtracting the objects in from the array.
Ex. if number is: 31 and the array {5,22,13,5,7,-4}.
Returns true because 22+13-4=31 .

A simple question for you: if the target number would've been 17 is the method supposed to return true also? (22-5 == 17)

kind regards,

Jos

[Yakg]

If there is a solution true, if it can't be reached then, false.

So what I'm planning to do is check for the next largest element each time
and if can't find one eventually and the result is !=number, then false.

[JosAH]

If there is a solution true, if it can't be reached then, false.

So what I'm planning to do is check for the next largest element each time
and if can't find one eventually and the result is !=number, then false.

If you are allowed to either add or subtract one of the numbers from the target number there's no need to sort those numbers in the array. Here's a bit of code that tries all combinations and tries to find the target number. Do with it what you want. The solve( ... ) method takes the following parameters:

1) the array of numbers.
2) the target number
3) the index of numbers that can still be used.
4) a list of the used numbers

import java.util.ArrayList;
import java.util.List;

public class T {

	private static void solve(int[] a, int sum, int i, List<Integer> terms) {
		if (sum == 0) {
			System.out.println(terms);
		}
		else if (i < a.length){
			solve(a, sum, i+1, terms);
			terms.add(a[i]);
			solve(a, sum-a[i], i+1, terms);
			terms.remove(terms.size()-1);
			terms.add(-a[i]);
			solve(a, sum+a[i], i+1, terms);
			terms.remove(terms.size()-1);
		}
	}
	
	public static void main(String[] args) {

		int[] a = {5,22,13,5,7,-4};
		solve(a, 31, 0, new ArrayList<Integer>());
	}
}

kind regards,

Jos

[Yakg]

could I use an array instead?
I will check if it works.

[JosAH]

could I use an array instead?
I will check if it works.

Internally an ArrayList<Integer> also uses an ordinary array so you can do it too; beware that you have to implement the nasty details of keeping track how many elements in the array are used, resizing the array when needed etc. yourself. Using an ArrayList<Integer> is much easier. On second thought, I'd better used a Stack<Integer> in my code ...

kind regards,

Jos

[Yakg]

sorry to bother but I trying to turn this method into boolean with no luck.
It is currently at its primary state.

private static boolean cover (int [] values, int amount, int i, List<Integer> mylist){
    if (amount == 0){
       System.out.println(mylist);
        }
    
    if (i<values.length){
        cover(values,amount,i+1,mylist);
        mylist.add(values[i]);
        cover(values,amount-values[i],i+1,mylist);
        mylist.remove(mylist.size()-1);
    }
    return true;
}

[Yakg]

the main:

public static void main(String[] args) {

int[] a = {5,22,13,5,7,-4};
System.out.print(cover(a, 31));
}
}

[JosAH]

sorry to bother but I trying to turn this method into boolean with no luck.
It is currently at its primary state.

private static boolean cover (int [] values, int amount, int i, List<Integer> mylist){
    if (amount == 0){
       System.out.println(mylist);
        }
    
    if (i<values.length){
        cover(values,amount,i+1,mylist);
        mylist.add(values[i]);
        cover(values,amount-values[i],i+1,mylist);
        mylist.remove(mylist.size()-1);
    }
    return true;
}

Your method always returns true at the end meaning to the caller of that method that it succeeded. You should only return true if the target amount == 0 or if one of the recursive invocations of that method returns true.

kind regards,

Jos

[gcalvin]

Start by identifying your base cases:

    public void test1() {
        int[] a = { };
        int t = 42;
        System.out.println("Should return false: " + cover(a, t));
    }

    public void test2() {
        int[] a = { };
        int t = 0;
        System.out.println("Should return true: " + cover(a, t));
    }

Now start to consider some other simple test cases in terms that will recurse to one of those base cases:

    public void test3() {
        int[] a = { 42 };
        int t = 42;
        System.out.println("Should return true: " + cover(a, t));
    }

    public void test4() {
        int[] a = { -42 };
        int t = 42;
        System.out.println("Should return true: " + cover(a, t));
    }

    public void test5() {
        int[] a = { 21 };
        int t = 42;
        System.out.println("Should return false: " + cover(a, t));
    }

Now consider carefully why each of these last three tests should return true or false, in terms of the base cases already defined. In other words, you want to recurse to an empty array, and either a zero test value (returns true) or a non-zero test value (returns false). Think about how you'll reduce the size of the array and change your test value for the recursive calls.

Since addition is commutative, you may consider the values in the array in any order without changing the result, so we may as well consider them in the order we receive them. That means for the first value n in the array and a test value t, we should consider:
1. t (unchanged) against the remaining values in the array (after removing n)
2. t + n against the remaining values in the array
3. t - n against the remaining values in the array

Hope that helps.

-Gary-

[NeuroFuzzy]

Errm, everyone's making it more complicated than it needs to be. It's easy to do this without arraylists! Well, I dunno about easy, but straightforward at least.

To solve recursive functions, you start programming a function assuming that it works.

Look at the code below, and work from the top of groupSumSub, like you've just wrote the class. First I figure "what are the 'base cases'/exit conditions?"
if target=0, then you don't need to add or subtract anything and you can return true. If start is bigger than the array, you can just return false.

We consider the first case now: if you add the number at start, can the numbers left over be combined to get target? That condition, "Can the numbers left over be combined to get the target" is the condition solved by groupSumSub, so we just call groupSumSub on the remaining numbers (start+1,nums), and subtract that number from the target. (in this way "target" represents the distance between the "current number" and the target.

The next case is the same thing but subtracting, so we instead add the current number.

If neither of those are true, then, if you add or subtract that number, there is no possible way you're reaching target. So we skip it, and just don't add anything to target, and move on to the next number!

	
public boolean solution(int[] nums, int target){return groupSumSub(0,nums,target);}

public boolean groupSumSub(int start, int[] nums, int target) 
	{
	  if(target==0)
	    return true;
	  if((start>=nums.length))
	    return false;

	  boolean temp=groupSumSub(start+1,nums,target-nums[start]);
	  if(temp)
	     return temp;

	  temp=groupSumSub(start+1,nums,target+nums[start]);
	  if(temp)
		  return temp;
	  
	  return groupSumSub(start+1,nums,target);
	}

also note, those last 10 lines could be replaced with:
return groupSumSub(start+1,nums,target-nums[start])||groupSumSub(start+1,nums,target-nums[start])||groupSumSub(start+1,nums,target+nums[start]);

but for clarity's sake...

[gcalvin]

NeuroFuzzy has a couple of good insights here:

1. As soon as you have a test value of 0 you can return true, no matter what's left in the array.
2. You don't need to resize the array if you can pass a starting index.

And since Java allows method overloading, you can do this:

    public static boolean cover(int[] a, int t) {
        // to cover the syntax of your main()
        return cover(a, t, 0);
    }

    public static boolean cover(int[] a, int t, int i) {
        // the real recursive method
        // TODO: write the rest of this
    }

-Gary-

[NeuroFuzzy]

Yeh, So this code would be my submission for best solution:

	public static boolean groupSumSub(int start, int[] nums, int target) 
	{
	  if(target==0) 
	    return true;
	  if(start>=nums.length)
	    return false;
	  return 	groupSumSub(start+1,nums,target-nums[start])||
	  			groupSumSub(start+1,nums,target+nums[start])||
	  			groupSumSub(start+1,nums,target);

	}

Here's a test program I made cuz I'm bored, verifying that my method works.

import java.util.List;
public class sum 
{
	public static String terms;
	public static void main(String[] args)
	{
		int[] arr1={1,2,3,4,5};
		int[] arr2={-1,-2,-3,-4,-5};
		int[] arr3={5,22,13,5,7,-4};
		int[] arr4={7,23,91,1};
		
		
		System.out.println(arrstr(arr1)+" : 15 -> "+solution(arr1,15)+"  15="+terms);
		System.out.println(arrstr(arr1)+" : 16 -> "+solution(arr1,16)+"  16="+terms);
		System.out.println(arrstr(arr1)+" : -15 -> "+solution(arr1,-15)+"  -15="+terms);
		System.out.println(arrstr(arr2)+" : 15 -> "+solution(arr2,15)+"  15="+terms);
		System.out.println(arrstr(arr3)+" : 31 -> "+solution(arr3,31)+"  31="+terms);
		System.out.println(arrstr(arr3)+" : 37 -> "+solution(arr3,37)+"  37="+terms);
		System.out.println(arrstr(arr4)+" : 30 -> "+solution(arr4,15)+"  30="+terms);
		System.out.println(arrstr(arr4)+" : 90 -> "+solution(arr4,15)+"  90="+terms);
		System.out.println(arrstr(arr4)+" : 89 -> "+solution(arr4,15)+"  89="+terms);
	}
	
	public static boolean solution(int[] nums, int target)
	{
		terms="";
		return groupSumSub(0,nums,target);
	}
	public static String arrstr(int[] arr)
	{
		String ret="{";
		for(int i=0;i<arr.length-1;i++)
		{
			ret+=arr[i]+",";
		}
		ret+=arr[arr.length-1]+"}";
		return ret;
	}

	public static boolean groupSumSub(int start, int[] nums, int target) 
	{
	  if(target==0)
	    return true;
	  if((start>=nums.length))
	    return false;

	  boolean temp=groupSumSub(start+1,nums,target-nums[start]);
	  if(temp)
	  {
		  
		 terms=terms+addnum(true,nums[start]);
	     return temp;
	  }
	  temp=groupSumSub(start+1,nums,target+nums[start]);
	  if(temp)
	  {
		  terms=terms+addnum(false,nums[start]);
		  return temp;
	  }
	  
	  return groupSumSub(start+1,nums,target);
	}
	public static String addnum(boolean positive, int num)
	{
		if(num>=0)
			if(positive)
				return "+"+num;
			else
				return "-"+num;
		if(num<0)
			if(positive)
				return ""+num;
			else
				return "+"+(0-num);
		return "";
	}
}

[JosAH]

Yeh, So this code would be my submission for best solution:

	public static boolean groupSumSub(int start, int[] nums, int target) 
	{
	  if(target==0) 
	    return true;
	  if(start>=nums.length)
	    return false;
	  return 	groupSumSub(start+1,nums,target-nums[start])||
	  			groupSumSub(start+1,nums,target+nums[start])||
	  			groupSumSub(start+1,nums,target);

	}

Your solution can't tell which numbers were used for the solution. My first method gives all the feasably solutions and I left it as an exercise to the OP to turn it in a boolean predicate. i.e. return as soon as a solution was found and unwind the recursion afterwards.

kind regards,

Jos

[NeuroFuzzy]

That wasn't the original problem, and if you look in the example code 1 post above my solution can be and was easily modified (If you want an arraylist replace the + String with a .add and an ArrayList)

;)