3ms c++ dfs solution


  • 0
    1

    Compared with Dp solution, the solution below pass OJ using just 3 ms, hope it helps;

    class Solution6 {
    public:
    	bool canPartition(vector<int> &nums) {
    		int sum = 0;
    		for (auto a : nums) {
    			sum += a;
    		}
    		if (sum % 2 != 0)
    			return false;
    		if (nums.size() <= 1)
    			return false;
    		target = sum / 2;
    		part[0] = 0;
    		part[1] = 0;
    		// sort in decsreasing order
    		std::sort(nums.begin(), nums.end(), [](const int &l, const int &r) {return l > r; });
    		return dfs(0, nums);
    
    	}
    private:
    	bool dfs(int index, vector<int> &nums) {
    		if (index == nums.size())
    			return part[0] == part[1];
    		for (int i = 0; i < 2; i++) {
    			if (part[i] + nums[index] > target)
    				continue;
    			// if we have check the same sum before,just ignore 
    			if (i == 1)
    				if (part[1] == part[0])
    					continue;
    			part[i] += nums[index];
    			if (dfs(index + 1, nums))
    				return true;
    			part[i] -= nums[index];
    		}
    		return false;
    	}
    	int target;
    	int  part[2];
    };
    

Log in to reply
 

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