LeetCode 77. Combinations 组合问题C(n,k)，树形状态回溯，优化减枝

77. Combinations

Given two integers n and k, return all possible combinations of k numbers out of 1 … n.

For example, If n = 4 and k = 2, a solution is:

[ [2,4], [3,4], [2,3], [1,2], [1,3], [1,4], ]

题意

给定两个整型数字，返回所有[1…n]之间k个元素的可能

思路

分析：在{1,2,3,4}四个数中，从左到右挨个选择一个数，当选择为1，进入到下一层，此时的选择范围变为{2,3,4}中从左到右选择一个数，当选择为2，此时path.size()等于k，保存路径{1,2}，开始回溯状态，将path中最后的一个元素弹出，继续在{3,4}中选择一个数，当选择为3，此时的path.size()等于k，保存路径{1,3}，继续回溯。。。。

k即为树形的高度

代码

for循环中是从index开始，是因为可用集合中元素只能使用一次，范围不断缩小对比131. Palindrome Partitioning class Solution { private: vector<vector<int>> res; // 求解C(n,k), 当前已经找到的组合存储在path中, 需要从index开始搜索新的元素 void findPath(int n,int k, int index, vector<int> path) { if(path.size() == k) //当找到的路径长度等于k，表示已经到底部，开始回溯 { res.push_back(path); return; } for(int i=index;i<=n;i++) //i是从index开始，表示可用区间为[index,n] { path.push_back(i); findPath(n,k,i+1,path); path.pop_back(); //状态回溯，回溯到path保存路径的上一层，继续进行遍历 } } public: vector<vector<int>> combine(int n, int k) { if(n<=0) { return res; } vector<int> path; findPath(n,k,1,path); return res; } };

优化减枝

通过观察树形图，发现当取了4之后，下一层没有可取的元素了才返回 改进:当元素不够时，完全可以不去取新的元素，将4的分支减去。

代码

缩小边界，只有当剩余的元素大于等于，满足路径的空位时，才继续 class Solution { private: vector<vector<int>> res; // 求解C(n,k), 当前已经找到的组合存储在path中, 需要从index开始搜索新的元素 void findPath(int n,int k, int index, vector<int> path) { if(path.size() == k) //当找到的路径长度等于k，表示已经到底部，开始回溯 { res.push_back(path); return; } // 还有k - path.size()个空位, 所以,[i...n]中至少要有k-path.size()个元素 //当k-path.size()等于1，那么i等于n, 当等于2,那么i等于n-1 // i最多为 n - (k-path.size()) + 1 for(int i=index;i<=n-(k-path.size())+1;i++) //i是从index开始，表示可用区间为[index,n] { path.push_back(i); findPath(n,k,i+1,path); path.pop_back(); //状态回溯，回溯到path保存路径的上一层，继续进行遍历 } return; } public: vector<vector<int>> combine(int n, int k) { if(n<=0) { return res; } vector<int> path; findPath(n,k,1,path); return res; } };

结果