[dfs] 473. Matchsticks to Square

Remember the story of Little Match Girl? By now, you know exactly what matchsticks the little match girl has, please find out a way you can make one square by using up all those matchsticks. You should not break any stick, but you can link them up, and each matchstick must be used exactly one time.

Your input will be several matchsticks the girl has, represented with their stick length. Your output will either be true or false, to represent whether you could make one square using all the matchsticks the little match girl has.

Example 1:
Input: [1,1,2,2,2]
Output: true

Explanation: You can form a square with length 2, one side of the square came two sticks with length 1.
Example 2:
Input: [3,3,3,3,4]
Output: false

Explanation: You cannot find a way to form a square with all the matchsticks.
Note:
The length sum of the given matchsticks is in the range of 0 to 10^9.
The length of the given matchstick array will not exceed 15.

想到的部分:把所有数字分为4组,使每组和为sum / 4。如果sum % 4 != 0 或者一共有小于4个数字就不可能形成正方形。分组的过程用dfs。
没想清楚的部分:dfs怎么实现。

public boolean makesquare(int[] nums) {
    if (nums == null || nums.length < 4) return false;
    int total = 0;
    for (int num : nums) total += num;
    if (total % 4 != 0) return false;
    return dfs(nums, total / 4, new int[4], 0);
}
    
private boolean dfs(int[] nums, int target, int[] sums, int index) {
    if (index == nums.length) {
        if (sums[0] == target && sums[1] == target && sums[2] == target) return true;
        return false;
    }
        
    for (int i = 0; i < 4; i++) { //尝试当前数字要加到哪个组
        if (sums[i] + nums[index] > target) continue;
        sums[i] += nums[index];
        if (dfs(nums, target, sums, index + 1)) return true;
        sums[i] -= nums[index];
    }
        
    return false;
}

本题需要找到4个sum,其实相对找到1个sum,增加的复杂度并不大,以下是另外一种实现,更加直接。
另,本来想到了,但是没有好好加进去的optimization:先sort数组,从最大数字开始尝试,这样如果不行会尽早发现。

    public boolean makesquare(int[] nums) {
        if (nums == null || nums.length < 4) return false;
        int total = 0;
        for (int num : nums) total += num;
        if (total % 4 != 0) return false;
        Arrays.sort(nums);
        long sum1 = 0, sum2 = 0, sum3 = 0, sum4 = 0;
        return dfs(nums, total / 4, sum1, sum2, sum3, sum4, nums.length - 1);
    }
    
    private boolean dfs(int[] nums, int target, long sum1, long sum2, long sum3, long sum4, int i) {
        if (sum1 > target || sum2 > target || sum3 > target || sum4 > target) return false;
        if (i == -1 && sum1 == target && sum2 == target && sum3 == target) return true;
        else if (i == -1) return false;
        
        return dfs(nums, target, sum1+nums[i], sum2, sum3, sum4, i-1) ||
               dfs(nums, target, sum1, sum2+nums[i], sum3, sum4, i-1) ||
               dfs(nums, target, sum1, sum2, sum3+nums[i], sum4, i-1) ||
               dfs(nums, target, sum1, sum2, sum3, sum4+nums[i], i-1);
    }
Advertisements

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s