C++ DFS find all permutation


  • 0
    B

    we can find all the permutation of the input array, then for each permutation we can evaluate the result from left to right or half and half.

    the complexity would be O(4! * 6^3), where 4! is number of all permutation, and two number can have 6 operation result, 4 number have 3 operations. After all, we cannot call it O(1). Should be O(n! * 6^(n-1)).

    class Solution {
    public:
        bool judgePoint24(vector<int>& nums) {
            return perm(nums, 0);
        }
        
        bool perm(vector<int>& nums, int idx)
        {
            if(idx == 3)
                return leftRight(nums) || halfHalf(nums);
            for(int j = idx; j < 4; j++)
            {
                if(j > idx && nums[j] == nums[idx]) continue;
                swap(nums[j], nums[idx]);
                if(perm(nums, idx+1)) return true;
                swap(nums[j], nums[idx]);            
            }
            return false;
        }
        
        bool leftRight(vector<int>& nums)
        {
            unordered_set<double> val1, val2;
            val1 = getVal(nums[0], nums[1]);
            for(auto e : val1)
            {
                unordered_set<double> tmp = getVal(e, nums[2]);
                val2.insert(tmp.begin(), tmp.end());
            }
            for(auto e : val2)
            {
                unordered_set<double> tmp = getVal(e, nums[3]);
                for(auto e : tmp)
                    if(e == 24) 
                        return true;
            }
            return false;
        }
        
        bool halfHalf(vector<int>& nums)
        {
            unordered_set<double> val1 = getVal(nums[0], nums[1]);
            unordered_set<double> val2 = getVal(nums[2], nums[3]);
            for(auto e : val1)
            {
                for(auto f : val2)
                {
                    unordered_set<double> tmp = getVal(e, f);
                    for(auto e : tmp)
                        if(e == 24) 
                            return true;
                }
            }
            return false;
        }
        
        unordered_set<double> getVal(double n1, double n2)
        {
            return unordered_set<double>{n1+n2, n1*n2, n1-n2, n2-n1, n1/(n2?n2:1), n2/(n1?n1:1)};
        }
    };

Log in to reply
 

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