JAVA DFS+DP solution


  • 3
    D
    public class Solution {
    	private Set<Integer> flags;
    
    	public boolean makesquare(int[] nums) {
    		if (nums.length == 0) return false;
    		int sum = 0;
    		for (int num : nums) {
    			sum += num;
    		}
    		if (sum % 4 != 0) return false;
    		flags = new HashSet<>();
    
    		dfs(nums, 0, sum / 4);
    
    		int len = (int) Math.pow(2, nums.length);
    		boolean[] dp = new boolean[len];
    		dp[0] = true;
    		for (int num : flags) {
    			for (int i = dp.length - 1; i >= 0; i--) {
    				if (dp[i] && (num&i)==0) {
    					dp[i | num] = true;
    				}
    			}
    		}
    		return dp[len - 1];
    	}
    
    	public void dfs(int[] nums, int flag, int sum) {
    		if (sum == 0) {
    			flags.add(flag);
    			return;
    		}
    		if (nums.length == 0) return;
    
    		if (nums[0] <= sum) {
    			dfs(Arrays.copyOfRange(nums, 1, nums.length), flag | (1 << nums.length - 1), sum - nums[0]);
    		}
    		dfs(Arrays.copyOfRange(nums, 1, nums.length), flag, sum);
    	}
    }
    

  • 0
    T

    This should be best solution!


Log in to reply
 

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