สมมติว่ามีตัวเลข ตัวเลขสามารถมองว่าเป็นผลคูณของตัวประกอบได้ เช่น 8 = 2 x 2 x 2; = 2 x 4 เราต้องทำฟังก์ชันที่รับจำนวนเต็ม n และคืนค่าการรวมตัวประกอบที่เป็นไปได้ทั้งหมด
เช่น ถ้าอินพุทเป็น 12 ผลลัพธ์จะเป็น [[2, 6], [2, 2, 3], [3, 4]]
เพื่อแก้ปัญหานี้ เราจะทำตามขั้นตอนดังนี้ −
กำหนดฟังก์ชัน solve() รับ n, target, start
กำหนดรายการรายการ ret
ถ้า n เท่ากับ 1 แล้ว −
คืนค่า ret
ถ้า n ไม่เท่ากับ target แล้ว −
แทรก n ที่ท้ายของ ret
ลูป i := start ถึง i * i <= n เพิ่ม i ทำ −
ถ้า n mod i เท่ากับ 0 แล้ว −
other = solve(n / i, target, i)
ลูป j := 0 ถึงขนาดของ other-1 ทำ −
แทรก i ที่ท้ายของ other[j]
แทรก other[j] ที่ท้ายของ ret
คืนค่า ret
จากเมธอดหลักทำดังนี้ −
คืนค่า solve(n, n, 2)
ตัวอย่าง
ลองดูการติดตั้งต่อไปนี้เพื่อให้เข้าใจได้ดีขึ้น −
#include <bits/stdc++.h> using namespace std; void print_vector(vector<vector<auto> > v){ cout << "["; for(int i = 0; i<v.size(); i++){ cout << "["; for(int j = 0; j <v[i].size(); j++){ cout << v[i][j] << ", "; } cout << "],"; } cout << "]"<<endl; } class Solution { public: vector < vector <int> > solve(int n, int target, int start){ vector < vector <int> > ret; if(n == 1){ return ret; } if(n != target){ ret.push_back({n}); } for(int i = start; i * i <= n; i++){ if(n % i == 0){ vector < vector <int> > other = solve(n / i, target,i); for(int j = 0; j < other.size(); j++){ other[j].push_back(i); ret.push_back(other[j]); } } } return ret; } vector<vector<int>> getFactors(int n) { return solve(n, n, 2); } }; main(){ Solution ob; print_vector(ob.getFactors(16)); } อินพุท
16
เอาต์พุท
[[8, 2, ],[4, 2, 2, ],[2, 2, 2, 2, ],[4, 4, ],]
