3ms C++ solution


  • 1
    D

    The method is applying DFS.

    class Solution {
    public:
        int cnt;
        bool makesquare(vector<int>& nums) {
            if (!nums.size()) return false;
            
            sort(nums.begin(), nums.end());
            reverse(nums.begin(), nums.end());
            
            int sum = 0;
            for (int n : nums) sum += n;
            if (sum % 4) return false;
            
            int target = sum / 4;
            cnt = 0;
            
            for (int i = 0; i < 4; i++) {
                vector<int> path;
                if (!dfs(nums, target, 0, path)) return false;
                for (int j = path.size()-1; j >= 0; j--) {
                    nums.erase(nums.begin()+path[j]);
                }
            }
            return true;
        }
        
        bool dfs(vector<int>& nums, int target, int start, vector<int>& path) {
            if (target == 0) {
                return true;
            }
            
            for (int i = start; i < nums.size(); i++) {
                if (nums[i] > target) continue;
                path.push_back(i);
                if (dfs(nums, target-nums[i], i+1, path)) return true;
                path.pop_back();
            }
            return false;
        }
    };
    
    

  • 0
    B

    Hi Dauphin7.

    In this approach, you first construct the first side completely choosing the largest elements possible. However, I am unable to reason the correctness of this approach. The code surely works though.
    Also, the complexity of 4 subset partition should be 4^n, but the complexity of this approach is only 4 * (2 ^ n).
    Could you explain how this sequential selection approach is equivalent to putting each array element in all 4 subsets and branching out.


  • 0
    D

    Hi, @bhavik92. My approach basically shares the same idea with those popular DFS method posts: here and here.

    The difference is:

    I assume in the true case , if we can find a list of numbers from the input whose sum equals to 1/4 of the sum of all numbers, then the remaining numbers in the input still have to consist of other three lengths. Once we find this list, we remove them from the input and turn the question into check if all the matchsticks could line up to three edges of the square. Admittedly, this assumption is based on my subjective feeling.

    To choose the largest elements first is to quickly find a valid list of numbers that can consist of an edge.


  • 0
    B

    Quite right. But by symmetry it should also work if the array is sorted in ascending manner.
    For eg. 11113333 even if it might be less efficient.
    In this case, the algorithm would pick 1111 first for one side. Now, clearly, other 3 sides can't be made to have equal sum.
    The correct solution is 31 31 31 31 which would indeed be picked if we go from largest to smallest. I am unable to come up with the counter example when we go from smallest to largest.


  • 0
    D

    @bhavik92 Oh yeah. The solution was written a month ago. I think I have tried in the ascending sort, but failed in test. Because of what you said made me use the descending sort. It might be explained in this way: if we choose longer sticks first, the remaining shorter sticks still could make a line as the same length as the longer one, while if we use shorter sticks first, the remaining longer sticks cannot provide you a length as the short one.


  • 0
    B

    Thanks for the explanation. Although its still not exactly clear to me, I think solution lies in the 'choosing longer sticks first' to maximize possibilites.


  • 0
    D

    @bhavik92 My bad, I should not to try to illustrate it concisely with at the cost of clarity. Let's try the last time. In the process of DFS (or backtracking), we process each case without knowing the future case.

    Now we need a certain length L, and have two options: 1) a (len(a) == L); and 2) b+c (len(b) + len(c) == L).

    After this step, we remove either a or (b and c) from the original array. Then we may need to deal with the remain stick(s) in three conditions:
    a) a case requires length of L;
    b) a case asks for len(b) and another case needs len(c);
    c) none of above.

    If we initially applied option 1), then we can deal with case a) and b); if we used option 2), we can only deal with case b), which may result in rejecting a true answer. For condition c), either option won't work, therefore, we would correctly reject a false answer.


Log in to reply
 

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