LeetCode link

first thought

  • first check the obvious situation such as the total sum can’t be divided by 4, or smaller than the maximum number * 4
  • same as the combination problem, from index 0 to end, recursively find the combination which added up is equal to sum / 4(square side length)
  • build a map to check the num is used or not, because each num can be used exactly once.

solution

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
public class Solution {
    public boolean makesquare(int[] nums) {
        if (nums == null || nums.length < 4) {
            return false;
        }
        int sum = 0;
        int max = 0;
        Map<Integer, Boolean> map = new HashMap<>();
        for (int i = 0; i < nums.length; i++) {
            sum += nums[i];
            map.put(i, false);
            max = Math.max(max, nums[i]);
        }
        int side = sum / 4;
        if (sum != side * 4 || sum < max * 4) {
            return false;
        }
        return this.helper(nums, side, side, 0, 0, map);
    }
    private boolean helper(int[] nums, int sum, int side, int sideCount, int index, Map<Integer, Boolean> map) {
        if (sideCount == 4) {
            return true;
        }
        if (sum == 0) {
            return this.helper(nums, side, side, sideCount + 1, 0, map);
        }
        if (index == nums.length || sum < 0) {
            return false;
        }
        boolean result = false;
        for (int i = index; i < nums.length; i++) {
            if (map.get(i) == false) {
                map.put(i, true);
                result = result || this.helper(nums, sum - nums[i], side, sideCount, i + 1, map);
                map.put(i, false);
                if (result) {
                    return true;
                }
            }
        }
        return result;
    }
}

problem

AC. But the time complexity is not good enough(118ms).

reason

  • check from the biggest num may reduce some time

modification

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
public class Solution {
    public boolean makesquare(int[] nums) {
        if (nums == null || nums.length < 4) {
            return false;
        }
        int sum = 0;
        int max = 0;
        Map<Integer, Boolean> map = new HashMap<>();
        for (int i = 0; i < nums.length; i++) {
            sum += nums[i];
            map.put(i, false);
            max = Math.max(max, nums[i]);
        }
        int side = sum / 4;
        if (sum != side * 4 || sum < max * 4) {
            return false;
        }
        Arrays.sort(nums);
        return this.helper(nums, side, side, 0, nums.length - 1, map);
    }
    private boolean helper(int[] nums, int sum, int side, int sideCount, int index, Map<Integer, Boolean> map) {
        if (sideCount == 4) {
            return true;
        }
        if (sum == 0) {
            return this.helper(nums, side, side, sideCount + 1, nums.length - 1, map);
        }
        if (index == -1 || sum < 0) {
            return false;
        }
        boolean result = false;
        for (int i = index; i >= 0; i--) {
            if (map.get(i) == false) {
                map.put(i, true);
                result = result || this.helper(nums, sum - nums[i], side, sideCount, i - 1, map);
                map.put(i, false);
                if (result) {
                    return true;
                }
            }
        }
        return result;
    }
}

problem

there is no difference…

modification

The fast solution check one side in the helper function. Mine is check one side and all sides in the helper using the params to control the recursion. I think there’s no difference, but just try it.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
public class Solution {
    public boolean makesquare(int[] nums) {
        if (nums == null || nums.length < 4) {
            return false;
        }
        int sum = 0;
        int max = 0;
        Map<Integer, Boolean> map = new HashMap<>();
        for (int i = 0; i < nums.length; i++) {
            sum += nums[i];
            map.put(i, false);
            max = Math.max(max, nums[i]);
        }
        int side = sum / 4;
        if (sum != side * 4 || sum < max * 4) {
            return false;
        }
        Arrays.sort(nums);
        for (int i = 0; i < 4; i++) {
            if (!this.helper(nums, side, nums.length - 1, map)) {
                return false;
            }
        }
        return true;
    }
    private boolean helper(int[] nums, int sum, int index, Map<Integer, Boolean> map) {
        if (sum == 0) {
            return true;
        }
        if (index == -1 || sum < 0) {
            return false;
        }
        for (int i = index; i >= 0; i--) {
            if (map.get(i) == false) {
                map.put(i, true);
                if (this.helper(nums, sum - nums[i], i - 1, map)) {
                    return true;
                }
                map.put(i, false);
            }
        }
        return false;
    }
}

result

AC(20ms). But still wondering what’s the difference, maybe the times of recursion loop. I’ll update this when I figure out the reason.