每日看点！n=4,k=2classSolution 如何遍历解空间树？

【资料图】

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