24点游戏算法

# -*- coding: utf-8 -*-


#
# 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
#
#
# @param nums int整型一维数组
# @return bool布尔型
#
class Solution:
    """
    题目：
        https://www.nowcoder.com/practice/36a06357855c4cd191f9d5ac8e75fec5?tpId=196&tqId=40440&rp=1&ru=/exam/oj&qru=/exam/oj&sourceUrl=%2Fexam%2Foj%3Fpage%3D7%26tab%3D%25E7%25AE%2597%25E6%25B3%2595%25E7%25AF%2587%26topicId%3D196&difficulty=undefined&judgeStatus=undefined&tags=&title=
    借鉴：
        牛客691957577号大神题解
    算法：
        定义process(sumnums, nums, combine)，sumnums表示当前表达式的和，nums表示当前剩余可选元素，combine表示已选的表达式
        如果nums为空，比较sumnums是否等于24：
            若相等：
                找到解，返回True
            否则：
                返回False
        否则：
            枚举可选元素，继续表达式计算，如果递归函数返回True，说明找到解。直接返回True即可
    复杂度：
        时间复杂度：O(n!), n为nums的长度
        空间复杂度：O(n)
    """

    def Point24(self, nums):
        # write code here
        def process(sumnums, nums, combine):
            if (len(nums) == 0):
                if sumnums == 24:
                    if combine[-1] == ")":  # 打印找到的表达式
                        combine = combine[1:-1]
                    print combine
                    return True
            for i in nums:
                a = nums[:]
                a.remove(i)
                addCombine = "(" + combine + "+" + str(i) + ")" \
                    if combine else str(i)
                subCombine = "(" + combine + "+" + str(i) + ")" \
                    if combine else str(i)
                divCombine = combine + "/" + str(i) if combine else str(i)
                mulCombine = combine + "*" + str(i) if combine else str(i)
                if process(sumnums + i, a, addCombine)&nbs***bsp;\
                        process(sumnums - i, a, subCombine)&nbs***bsp;\
                        process(sumnums / i, a, divCombine)&nbs***bsp;\
                        process(sumnums * i, a, mulCombine):
                    return True
            return False

        return process(0.0, nums, "")


if __name__ == "__main__":
    sol = Solution()

    # nums = [7, 2, 1, 10]

    # nums = [6, 4, 2, 7]

    nums = [2, 2, 3, 3]

    # nums = [6, 6, 6, 6]

    res = sol.Point24(nums)

    print res

# 牛客评论有bug，python2的or识别有误

class Solution {
  public:
    bool Point24(vector<int>& nums) {
        vector<char> ops = {'+', '-', '*', '/'};
        return dfs(nums, ops);
    }

    bool dfs(vector<int>& nums, vector<char>& ops) {
        if (nums.size() == 1) {
            return abs(nums[0] - 24) < 1e-6;
        }
        for (int i = 0; i < nums.size(); i++) {
            for (int j = 0; j < nums.size(); j++) {
                if (i == j) {
                    continue;
                }
                vector<int> new_nums;
                for (int k = 0; k < nums.size(); k++) {
                    if (k != i && k != j) {
                        new_nums.push_back(nums[k]);
                    }
                }
                for (auto op : ops) {
                    if (op == '+') {
                        new_nums.push_back(nums[i] + nums[j]);
                    } else if (op == '-') {
                        new_nums.push_back(nums[i] - nums[j]);
                    } else if (op == '*') {
                        new_nums.push_back(nums[i] * nums[j]);
                    } else if (op == '/') {
                        if (abs(nums[j]) < 1e-6 || nums[i] % nums[j] != 0) {
                            continue;
                        }
                        new_nums.push_back(nums[i] / nums[j]);
                    }
                    if (dfs(new_nums, ops)) {
                        return true;
                    }
                    new_nums.pop_back();
                }
            }
        }
        return false;
    }
};