Programming Interview 32: Write a Solution for Twenty-Four game

Step by step to crack Programming Interview questions 32: Write a Solution for Twenty-Four game
Given 4 numbers within [1,10], return arithmetic way to compute 24 or return null if not possible
E.g. 1,2,3,4, return 1*2*3*4=24; 8,8,9,9, return null

Solution (recursive way)
1. Divide-and-conquer

2. Start from simpler scenario to more difficult cases
2.1. Given two numbers, how to compute 24
2.2. Extend to three numbers, choose two numbers, compute the result and together with 3rd number to try compute 24
2.3. Extend to four numbers, choose two numbers, compute the result of two number and apply to 3-number scenario

3. Pay attention to the Data type returned
3.1. A Boolean signal to indicate success/failure for back-tracing
3.1.1. We immediately stop when a success solution found
3.2. A String expression to record the way to compute 24

4. Use floating numbers instead of integer for computing process (e.g. (3+3/7)*7=24)

[AI_Edu_]

Thanks. I was actually interviewed with this problem before, but that's not a coding questions, instead it's a discussion question after the coding phase. I am sure the code logic can be improved so it's more understandable, but I'd even prefer if some people can paste their own code or some great resource to do the work for me. So if you had your own solution, please please paste it here so I can also learn. Thanks

[zbpl]

you're right only those 2 are needed. but i wanted to keep the order of numbers

[AI_Edu_]

Thanks for sharing. Our basic idea is same.
I am curious about the '5 combinations of brackets', why only 5? Can it be simplified to only two? In total we have the following 10 different ways to put parenthesis.
1. (ab)cd
2. a(bc)d
3. ab(cd)
4. (abc)d
5. a(bcd)
6. ((ab)c)d
7. (a(bc))d
8. a((bc)d)
9. a(b(cd))
10. (ab)(cd)
Because of the permutation of numbers, I guess we only need case #6 and #10. Other cases can be mapped to the chosen 2 (some unnecessary parenthesis may be added)?

[AI_Edu_]

I think so. If you can also share you solution that will be awesome~ Thanks.

[AI_Edu_]

Thanks to RoadRelly, I have identified the bug in my code when making the video. The source code can be downloaded at goo.gl(slash)HO2a1, which fixed both the parenthesis problem and the bad case (9, 7, 10, 5) issue. The reason causing the bug is the order of the sub-result should be tried all 3 different positions when we simply the 4-number problem to 3-number problem.

[zbpl]

well, i wrote it different way and 9, 7, 10, 5 can be solved!
what about 9-(7-10)*5 for signed, or (10-7)*5+9 for unsigned

[AI_Edu_]

Thank you. I re-test my code, it seems my code is sensitive the order the numbers coming and this is a bug. Could you share you solution please?

[fishmillionsfish]

The code is too length for an interview, can we use recursion to do this?