每日讯息!n=4,k=2classSolution 如何遍历解空间树?

发布时间:   来源:CSDN  


(资料图片)

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;    }};

相关文章Related

返回栏目>>