C++_13ms_Backtracking_DFS_Accepted


  • 0

    (At first I thought it could be solved by the two pointers.)

    • Find out the sum of the vector. If sum is odd, then return false, because we could not divide odd number into the sum of two equal numbers.

    • Sort this vector. Using the backtracking method, if we find the add == target return true; if we find the add is larger than our target, break and return false; else we can keep on finding the elements.

    Code:

    class Solution {
    public:
    bool canPartition(vector<int>& nums) {
        int target = 0;
        for(auto num:nums){target += num;}
        if(target % 2) return false;
        target = target/2;
    
        sort(nums.begin(), nums.end());
        return find(nums, target, 0, 0);
    }
    
    bool find(vector<int>& nums, int target, int add, int begin){
        if(add == target){return true;}
        else if(add > target){return false;}
        for(int i = begin; i < nums.size(); i++){
            add += nums[i];
            if(find(nums, target, add, i+1)){return true;}
            add -= nums[i];
        }
        return false;
    }
    };

Log in to reply
 

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