【递归】 LeetCode473. 火柴拼正方形

梦里梦外; 2022-12-03 05:22 157阅读 0赞

### 题目 ###

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3UwMTE3MjYwMDU_size_16_color_FFFFFF_t_70_pic_center]![在这里插入图片描述][20200901213721948.png_pic_center]

### 解答 ###

> 回溯法的求解过程实质上是一个先序遍历一棵状态树的过程，只是这棵树不是遍历前预先建立的，而是隐含在遍历的过程中。

> 递归题的解法：首先把题目的决策树画出来，树的层就是for循环，树的深度就是要递归的参数i。画出决策树后，找规律，进行剪枝。

**E.g.** 输入【1, 1, 2, 2, 2】

放小球问题，总共四个盒子，每个数从大到小依次网盒子里放，**放满则放到下一个盒子**。  
首先将所有的数进行从大到小排序，先放大的，后放小的。

树层为四个盒子，树的深度为每个数。  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3UwMTE3MjYwMDU_size_16_color_FFFFFF_t_70_pic_center 1]

### 代码 ###

#include <iostream>
    #include <string>
    #include <list>
    #include <vector>
    #include <map>
    #include <utility>
    #include <functional>
    #include <algorithm>
    #include <numeric>
    #include <cassert>
    
    // 473. Matchsticks to Square
    
    // 正方形的四条边恰好相当于四个盒子，然后依次向每个盒子里面放入给定小球，如果一个盒子放满了则放到下一个盒子里。
    bool AddStick(int i, const std::vector<int>& nums, int target_side_len, int side_sums[4]) { 
      if (i >= nums.size()) { 
        if (side_sums[0] == target_side_len &&
            side_sums[1] == target_side_len &&
            side_sums[2] == target_side_len &&
            side_sums[3] == target_side_len) { 
          return true;
        }
    
        return false;
      }
    
      for (int j = 0; j < 4; ++j) { 
        // nums[i]不合适放入当前盒子，则放入下一个盒子。
        if (side_sums[j] + nums[i] > target_side_len) { 
          continue;
        }
        
        side_sums[j] += nums[i];
    
        // 在当前的盒子放入下一个数
        if (AddStick(i + 1, nums, target_side_len, side_sums)) { 
          return true;
        }
    
        // 尝试完这个数恢复之前的状态, 然后放入下一个盒子。
        side_sums[j] -= nums[i];
      }
    
      return false;
    }
    
    bool makesquare1(std::vector<int> nums) { 
      if (nums.size() < 4) { 
        return false;
      }
    
      // 对于递归在题目中提前找到剪枝条件十分重要。
      int sum = std::accumulate(nums.begin(), nums.end(), 0);
      if (sum % 4 != 0) { 
        return false;
      }
    
      int side_length = sum / 4;
      for (int num : nums) { 
        if (num > side_length) { 
          return false;
        }
      }
    
      // 由大到小排序,该条件至关重要。
      // 由大到小排序后，可以极大地减少递归的次数。
      std::sort(nums.begin(), nums.end(), std::greater<int>());
    
      int side_sums[4] = {  0 };
    
      return AddStick(0, nums, side_length, side_sums);
    }
    
     int main() { 
      std::cout << makesquare1({  1, 1, 2, 2, 2 }) << std::endl;
      std::cout << makesquare1({  3, 3, 3, 3, 4 }) << std::endl;
      std::cout << makesquare1({  8, 16, 24, 32, 40, 48, 56, 64, 72, 80, 88, 96, 104, 112, 60 }) << std::endl;
      std::cout << makesquare1({  5, 5, 5, 5, 16, 4, 4, 4, 4, 4, 3, 3, 3, 3, 4 }) << std::endl;
    
      return 0;
    }

[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3UwMTE3MjYwMDU_size_16_color_FFFFFF_t_70_pic_center]: https://img-blog.csdnimg.cn/20200901213713479.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3UwMTE3MjYwMDU=,size_16,color_FFFFFF,t_70#pic_center
[20200901213721948.png_pic_center]: /images/20221123/3b7cc0dad1c4464cba168cbc6c048e58.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3UwMTE3MjYwMDU_size_16_color_FFFFFF_t_70_pic_center 1]: /images/20221123/ca7ee7fb3f8e487ebabd18b35aa8bf50.png