java dfs solution


  • 1
    2

    Note: we always try longer stick first.

    public class Solution {
        public boolean makesquare(int[] nums) {
            if (nums.length == 0) {
                return false;
            }
            int sum = 0;
            for (int i : nums) {
                sum += i;
            }
            if (sum % 4 != 0) {
                return false;
            }
            Arrays.sort(nums);
            return dfs(nums, new boolean[nums.length], sum / 4, 0, 4, nums.length);
        }
        private boolean dfs(int[] nums, boolean[] visited, int edgeLen, int len, int n, int max) {
            if (n == 0) {
                return true;
            }
            if (len > edgeLen) {
                return false;
            }
            if (len == edgeLen) {
                return dfs(nums, visited, edgeLen, 0, n - 1, nums.length);
            }
            for (int i = max - 1; i >= 0; i--) {
                if (visited[i]) {
                    continue;
                }
                visited[i] = true;
                if (dfs(nums, visited, edgeLen, len + nums[i], n, i)) {
                    return true;
                }
                visited[i] = false;
            }
            return false;
        }
    }
    

  • 0
    J

    Thanks for sharing. I didn't use "i" as the "max" in the dfs and always get TLE. Your solution helped me in figuring out that.


Log in to reply
 

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