每日訊息!n=4,k=2classSolution 如何遍歷解空間樹？

來源：CSDN 時間：2023-03-23 15:49:22

(資料圖片)

n=4, k=2

class Solution {public: vectorans; vectorchoice; void func(int startIndex, int n, int k){if(choice.size() == k){ans.push_back(choice); return; } for(int i = startIndex; i < n; i++){choice.push_back(i + 1); func(i + 1, n, k); choice.pop_back(); } } vectorcombine(int n, int k) {func(0, n, k); return ans; }};

優化

如果按照我們上面代碼的思路，整個解空間樹都會被遍歷到，而實際上，這些紅叉的路徑是不需要遍歷的，因為他們遍歷下去根本就不會到達第3層，即無法挑選出3個元素

如果我們此時沒有選擇元素，choice.size()=0，i=0，按照圖中解空間樹，我們不能從下標為3的元素4開始遍歷

如果我們此時選擇下標為0的元素1，choice.size()=1，進入下一層i=1，按照圖中解空間樹，我們不能從下標為4的元素5開始遍歷

如果我們此時選擇下標為1的元素2，choice.size()=1，進入下一層i=1，按照圖中解空間樹，我們不能從下標為4的元素5開始遍歷

choice.size()表示已經選擇的元素數量，n表示元素的總數量，k表示需要選擇的元素數量，i表示當前下標（已經進入了下一層，i+1了）。我們需要剩下能選擇的元素數量（n-i）能夠供應還需要的元素數量（k-choice.size()）。所以我們有：

k ? c h o i c e . s i z e ( ) < = n ? i k-choice.size()<=n-i k?choice.size()<=n?i，即 i < = n ? ( k ? c h o i c e . s i z e ( ) ) i<=n-(k-choice.size()) i<=n?(k?choice.size())

class Solution {public: vectorans; vectorchoice; void func(int startIndex, int n, int k){if(choice.size() == k){ans.push_back(choice); return; } for(int i = startIndex; i <= n-(k-choice.size()); i++){choice.push_back(i + 1); func(i + 1, n, k); choice.pop_back(); } } vectorcombine(int n, int k) {func(0, n, k); raeturn ans; }};

責任編輯：

標簽：

上一篇：天天消息！appleappstore怎么設置？appleappstore重啟電腦方法
下一篇：最后一頁