c++ backtracking solution, 6ms.


  • 5
    H
    class Solution {
    public:
        bool canPartition(vector<int>& nums) {
            int sum = 0;
            for(int i =0;i<nums.size();i++){
                sum+= nums[i];
            }
            if(sum%2) return false;
            sum /= 2;
            sort(nums.rbegin(),nums.rend());
            return helper(nums, sum, 0);
        }
        bool helper(vector<int>& nums, int sum, int index){
            if(sum == nums[index]) return true;
            if(sum < nums[index]) return false;
            return helper(nums,sum-nums[index],index+1) || helper(nums,sum,index+1);
        }
    };
    

  • 1
    D

    At first glance, it seems it is just naive DFS without memorization. I am actually a bit confused about why it is so fast. Am I missing something here?


  • 1
    Y

    'Cuz the posted code did very good pruning by sorting the vector in decreasing order.


Log in to reply
 

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