My recursive java solution

• ``````public class Solution {
public List<Integer> diffWaysToCompute(String input) {
List<Integer> list=new ArrayList();
if(input==null||input.length()==0) return list;
if(!input.contains("+")&&!input.contains("-")&&!input.contains("*")) {
return list;
}
for(int i=0;i<input.length();i++){
char ops=input.charAt(i);
if(ops=='+'||ops=='-'||ops=='*'){
List<Integer> leftList=diffWaysToCompute(input.substring(0,i));
List<Integer> rightList=diffWaysToCompute(input.substring(i+1,input.length()));
for(int leftValue:leftList){
for(int rightValue:rightList){
switch(ops){
}
}
}
}
}
return list;
}
``````

}

• What is the complexity of this solution?

• @Pezhang

complexity

I think it is n!.
For the first round, you have n-1 choices to combine any 2 numbers. In the second round, you have n-2 choices, .... So, it is: (n-1)(n-2)(n-3)....*1

• Very concise solution. I came up with one similar with yours. But didn't implement it successfully. :/

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.