473. Matchsticks to Square

class Solution {
    public boolean makesquare(int[] nums) {
        if (nums.length == 0) return false;
        int n = nums.length;
        Arrays.sort(nums);

        int sum = 0;
        for (int num : nums) {
            sum += num;
        }

        if (sum % 4 != 0) return false;

        return dfs(nums, 0, 0, sum / 4, 1, new boolean[n]);
    }

    private boolean dfs(int[] nums, int index, int tmp, int target, int group, boolean[] visited) {
        if (group == 4) return true;
        if (tmp > target) return false;
        if (target == tmp) return dfs(nums, 0, 0, target, group + 1, visited);

        for (int i = index; i < nums.length; i++) {
            if (visited[i]) continue;
            if (i > 0 && nums[i] == nums[i - 1] && !visited[i - 1]) continue;
            visited[i] = true;
            if (dfs(nums, i + 1, tmp + nums[i], target, group, visited)) return true;
            visited[i] = false;
        }

        return false;
    }
}