Computing target number from numbers in a set

Question

I'm working on a homework problem that asks me this:

Tiven a finite set of numbers, and a target number, find if the set can be used to calculate the target number using basic math operations (add, sub, mult, div) and using each number in the set exactly once (so I need to exhaust the set). This has to be done with recursion.

So, for example, if I have the set

{1, 2, 3, 4}

and target 10, then I could get to it by using

((3 * 4) - 2)/1 = 10. 

I'm trying to phrase the algorithm in pseudo-code, but so far haven't gotten too far. I'm thinking graphs are the way to go, but would definitely appreciate help on this. thanks.

Answer 1

This isn't meant to be the fastest solution, but rather an instructive one.

• It recursively generates all equations in postfix notation
• It also provides a translation from postfix to infix notation
• There is no actual arithmetic calculation done, so you have to implement that on your own
  • Be careful about division by zero

With 4 operands, 4 possible operators, it generates all 7680 = 5 * 4! * 4^3 possible expressions.

• 5 is Catalan(3). Catalan(N) is the number of ways to paranthesize N+1 operands.
• 4! because the 4 operands are permutable
• 4^3 because the 3 operators each have 4 choice

This definitely does not scale well, as the number of expressions for N operands is [1, 8, 192, 7680, 430080, 30965760, 2724986880, ...].

In general, if you have n+1 operands, and must insert n operators chosen from k possibilities, then there are (2n)!/n! k^n possible equations.

Good luck!

import java.util.*;

public class Expressions {
    static String operators = "+-/*";

    static String translate(String postfix) {
        Stack<String> expr = new Stack<String>();
        Scanner sc = new Scanner(postfix);
        while (sc.hasNext()) {
            String t = sc.next();
            if (operators.indexOf(t) == -1) {
                expr.push(t);
            } else {
                expr.push("(" + expr.pop() + t + expr.pop() + ")");
            }
        }
        return expr.pop();
    }

    static void brute(Integer[] numbers, int stackHeight, String eq) {
        if (stackHeight >= 2) {
            for (char op : operators.toCharArray()) {
                brute(numbers, stackHeight - 1, eq + " " + op);
            }
        }
        boolean allUsedUp = true;
        for (int i = 0; i < numbers.length; i++) {
            if (numbers[i] != null) {
                allUsedUp = false;
                Integer n = numbers[i];
                numbers[i] = null;
                brute(numbers, stackHeight + 1, eq + " " + n);
                numbers[i] = n;
            }
        }
        if (allUsedUp && stackHeight == 1) {
            System.out.println(eq + " === " + translate(eq));
        }
    }
    static void expression(Integer... numbers) {
        brute(numbers, 0, "");
    }

    public static void main(String args[]) {
        expression(1, 2, 3, 4);
    }
}

Answer 2

Before thinking about how to solve the problem (like with graphs), it really helps to just look at the problem. If you find yourself stuck and can't seem to come up with any pseudo-code, then most likely there is something that is holding you back; Some other question or concern that hasn't been addressed yet. An example 'sticky' question in this case might be, "What exactly is recursive about this problem?"

Before you read the next paragraph, try to answer this question first. If you knew what was recursive about the problem, then writing a recursive method to solve it might not be very difficult.

You want to know if some expression that uses a set of numbers (each number used only once) gives you a target value. There are four binary operations, each with an inverse. So, in other words, you want to know if the first number operated with some expression of the other numbers gives you the target. Well, in other words, you want to know if some expression of the 'other' numbers is [...]. If not, then using the first operation with the first number doesn't really give you what you need, so try the other ops. If they don't work, then maybe it just wasn't meant to be.

Edit: I thought of this for an infix expression of four operators without parenthesis, since a comment on the original question said that parenthesis were added for the sake of an example (for clarity?) and the use of parenthesis was not explicitly stated.