algorithm - 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);
    }
}