02 Jan 2017

# Recursion to divide and conquer II

Author: derek0883@gmail.com

This example will show you how to use recursion method solve problem, then lead to two Divide and Conquer solution.

## Different Ways to Add Parentheses

Given a string of numbers and operators, return all possible results from computing all the different possible ways to group numbers and operators. The valid operators are +, - and *.

``````Example 1
Input: "2-1-1".

((2-1)-1) = 0
(2-(1-1)) = 2
Output: [0, 2]

Example 2
Input: "2*3-4*5"

(2*(3-(4*5))) = -34
((2*3)-(4*5)) = -14
((2*(3-4))*5) = -10
(2*((3-4)*5)) = -10
(((2*3)-4)*5) = 10
Output: [-34, -14, -10, -10, 10]
``````

### Video explanation

## Divide and Conquer

Recursion method is all about how many option you have in each step, if you have N option, then divide it into N sub problem. Here the number of option is number of operator we have. Instead of evaluate that option first, we will evaluate that option last, this is much better to handle duplicate case and multiple sub-string.

``````public class DifferentWays {
public List<Integer> diffWaysToCompute(String input) {
if (input.isEmpty())
return null;
return diffWaysToCompute(input, 0, input.length()-1);
}
boolean isOprator(char ch) {
return ch == '+' || ch == '-' || ch == '*';
}
private static int cal(int left, int right, char operator) {
if (operator == '+') {
return left + right;
} else if (operator == '-') {
return left - right;
} else {
return left * right;
}
}
public List<Integer> diffWaysToCompute(String input, int L, int R) {
List<Integer> all = new ArrayList<Integer>();
List<Integer> left;
List<Integer> right;
for (int i = L; i <= R; i++) {
if (isOprator(input.charAt(i))) {
left = diffWaysToCompute(input, L, i-1);
right = diffWaysToCompute(input, i+1, R);
for (int l : left) {
for (int r : right) {