สมมุติว่ามีสาวจับคู่ตัวเล็กๆ และเรารู้ว่าไม้ขีดไฟที่สาวน้อยจับคู่มีอะไรบ้าง เราต้องหาวิธีสร้างสี่เหลี่ยมจัตุรัสโดยใช้ไม้ขีดไฟเหล่านั้นให้หมด เราไม่ควรหักไม้ใด ๆ แต่เราสามารถเชื่อมโยงมันได้ และไม้ขีดไฟแต่ละอันต้องใช้เพียงครั้งเดียวเท่านั้น ข้อมูลของเราจะเป็นไม้ขีดไฟหลายอันที่เด็กผู้หญิงคนนั้นมี ซึ่งแสดงด้วยความยาวของไม้ขีด ผลลัพธ์ของเราจะเป็นจริงหรือเท็จ เพื่อแสดงว่าเราสามารถสร้างสี่เหลี่ยมจัตุรัสโดยใช้ไม้ขีดไฟทั้งหมดที่สาว ๆ จับคู่มีได้หรือไม่ ดังนั้นหากอินพุตเป็น [1,1,2,2,2] คำตอบจะเป็นจริง เนื่องจากเราสามารถสร้างกำลังสองที่มีความยาว 2 ด้านหนึ่งจะมีแท่งยาว 2 แท่ง 1
เพื่อแก้ปัญหานี้ เราจะทำตามขั้นตอนเหล่านี้ -
- กำหนดวิธีการเรียกซ้ำที่เรียกว่า Solve() สิ่งนี้จะใช้ดัชนี, ผลรวมอาร์เรย์, เป้าหมายและอาร์เรย์ nums จะได้ผลดังนี้ −
- ถ้าดัชนี>=ขนาด nums แล้ว
- คืนค่าเป็น true เมื่อ sums[0], sum[1] และ sum[2] เหมือนกันกับผู้กำหนดเป้าหมาย
- สำหรับ i ในช่วง 0 ถึง 3 −
- ถ้า sums[i] + nums[index]> เป้าหมาย ให้ข้ามส่วนถัดไปของลูป
- sums[i] :=sums[i] + nums[index]
- ถ้าแก้ (ดัชนี + 1, ผลรวม, เป้าหมาย, ตัวเลข) เป็นจริง ให้คืนค่าจริง
- sums[i] :=sums[i] – nums[index]
- คืนค่าเท็จ
- จากวิธีหลัก ให้ทำดังต่อไปนี้ −
- ถ้า nums ไม่มีองค์ประกอบ ให้คืนค่าเท็จ
- x :=0
- สำหรับ i ในช่วง 0 ถึงขนาดของ nums ให้เพิ่ม x โดย nums[j]
- ถ้า x หารด้วย 4 ลงตัว ให้คืนค่าเท็จ
- เรียงลำดับอาร์เรย์ nums
- สร้างผลรวมอาร์เรย์ของขนาด 4
- ผลตอบแทนแก้(0, ผลรวม, x/4, ตัวเลข)
ให้เราดูการใช้งานต่อไปนี้เพื่อความเข้าใจที่ดีขึ้น -
ตัวอย่าง
#include <bits/stdc++.h>
using namespace std;
class Solution {
public:
bool solve(int idx, vector <int>& sums, int target, vector <int>& nums){
if(idx >= nums.size()){
return sums[0] == sums[1] && sums[1] == sums[2] && sums[2] == target;
}
for(int i = 0; i < 4; i++){
if(sums[i] + nums[idx] > target)continue;
sums[i] += nums[idx];
if(solve(idx + 1, sums, target, nums)) return true;
sums[i] -= nums[idx];
}
return false;
}
bool makesquare(vector<int>& nums) {
if(nums.size() == 0) return false;
int x = 0;
for(int i = 0; i < nums.size(); i++){
x += nums[i];
}
if(x % 4) return false;
sort(nums.rbegin(), nums.rend());
vector <int> sum(4);
return solve(0, sum,x / 4, nums);
}
};
main(){
vector<int> v = {1,1,2,2,2};
Solution ob;
cout << (ob.makesquare(v));
} อินพุต
[1,1,2,2,2]
ผลลัพธ์
1
