每日讯息!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重启电脑方法
下一篇：最后一页