Java dfs solution, 7ms


  • 0
    W
    public boolean canPartition(int[] nums) {
    	int sum = 0;
    	for(int i = 0; i < nums.length; i++) {
    		sum += nums[i];
    	}
    	if(sum % 2 != 0) {
    		return false;
    	}
    	sum /= 2;
    	
    	return dfs(nums, 0, sum);
    	
    }
    
    public boolean dfs(int[] nums, int from, int sum) {
    	if(sum == 0) {
    		return true;
    	} else if(sum < 0) {
    		return false;
    	}
    	
    	boolean flag = false;
    	
    	for(int i = from; i < nums.length; i++) {
    		flag |= dfs(nums, i + 1, sum - nums[i]);
    		if(flag == true)
    			return true;
    	}
    	
    	return false;	
    }

  • 0

    @Whentao You can just write:

    if(dfs(nums, i + 1, sum - nums[i])) return true;
    

    instead of

    flag |= dfs(nums, i + 1, sum - nums[i]);
    if(flag == true) return true;
    

  • 0
    T

    Your solution will get runtime error...


  • 0
    W

    @ttylcc the test case may change. Maybe you can use dp to solve this problem.


  • 0
    T

    that's true. the data points are under 100, so dfs is not a good idea.


  • 0

    Time Limit Exceeded


  • 0
    W

    @nova0930 hi~ This is an out of date solution, just for the contest 8 and the test case changed 3 months ago. You can use dp to solve this problem and dp is really fast.


Log in to reply
 

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