Backtracking Approach for LeetCode Problem 679: 24 Game

示例 1:
输入: [4, 1, 8, 7]
输出: True
解释: (8-4) * (7-1) = 24

示例 2:
输入: [1, 2, 1, 2]
输出: False

注意:
除法运算符 / 表示实数除法，而不是整数除法。
例如 4 / (1 - 2/3) = 12 。

每个运算符对两个数进行运算。特别是我们不能用 - 作为一元运算符。
例如，[1, 1, 1, 1] 作为输入时，表达式 -1 - 1 - 1 - 1 是不允许的。

你不能将数字连接在一起。
例如，输入为 [1, 2, 1, 2] 时，不能写成 12 + 12 。

class Solution {
	bool can = false;
public:
    bool judgePoint24(vector<int>& nums) {
    	vector<double> number(4);
        for(int i = 0; i < 4; ++i)
            number[i] = double(nums[i]);
    	check(number);
    	return can;
    }
    void check(vector<double>& nums) 
    {
    	if(can) return;
    	if(nums.size() == 1)
    	{
    		if(fabs(nums[0]-24) < 1e-6)
    			can = true;
    		return;
    	}
    	for(int i = 0; i < nums.size(); i++)
    	{
    		for(int j = 0; j < nums.size(); j++)
    		{
    			if(i == j)
    				continue;
    			vector<double> temp;
    			for(int k = 0; k < nums.size(); k++)
    				if(k != i && k != j)
    					temp.push_back(nums[k]);//剩余数字直接放进数组
    			for(int k = 0; k < 4; k++)
    			{
    				if(k < 2 && i > j)
    					continue;// + * 法满足交换律
    				if(k == 0)
    					temp.push_back(nums[i]+nums[j]);
    				else if(k == 1)
    					temp.push_back(nums[i]*nums[j]);
    				else if(k == 2)
    					temp.push_back(nums[i]-nums[j]);
    				else
    					temp.push_back(nums[i]/nums[j]);
    				check(temp);
    				temp.pop_back();//回溯
    			}
    		}
    	}
    }
};