组合
递归是深度，for是广度
n=4 ，k =2 ,两层递归，for遍历4
回溯遍历法
class Solution { public: vector<vector<int>> result; vector<int> path; //left是for的开始 ，right是for的结束。当size==k的时候递归结束 void tarversal(int left , int right , int k) { if(path.size() == k) { result.push_back(path); return; }else { for(int i= left ; i <= right ; i++) { path.push_back(i); tarversal(i+1 ,right , k); path.pop_back(); } return; } } vector<vector<int>> combine(int n, int k) { tarversal(1,n,k); return result; } };
回溯剪枝法
剪枝是减少无意义循环的过程
当输入是n=4，k=4的时候，只有1234符合。我们遍历到2开始时，最多为234，234的长度为3满足长度为4的情况，是无意义的，要剪去。
for(int i= left ; i <= right - (k - path.size()) +1 ; i++) 为剪枝的判断
其中left为遍历的开始，right为遍历的结束。现在还需要找到k - path.size()个点
即 right - left => (k - path.size()) ，为剩下的点可以满足k的要求
=>left <= right - (k - path.size()) +1 ， 其中+1为满足左边闭合。
例，k=3，n=4时，已经选取的为0个（path.size()=0），带入i <= right - ( k - path.size() ) +1 ， i <= 4 - （3-0）+1 ，为i<=2。
即当i最大为从2开始满足，为234 。大于2 剪枝
class Solution { public: vector<vector<int>> result; vector<int> path; void tarversal(int left , int right , int k) { if(path.size() == k) { result.push_back(path); return; }else { //i <= right - (k - path.size()) +1为剪枝的过程，避免无意义的循环 for(int i= left ; i <= right - (k - path.size()) +1 ; i++) { path.push_back(i); tarversal(i+1 ,right , k); path.pop_back(); } return; } } vector<vector<int>> combine(int n, int k) { tarversal(1,n,k); return result; } };
二刷
class Solution { public: vector<vector<int>> result; vector<int> combinNum; void track_back(int n , int k ,int fir) { if(combinNum.size() == k) { result.push_back(combinNum); return; } for(int i=fir+1 ; i<=n ; i++) { combinNum.push_back(i); track_back(n,k,i); combinNum.pop_back(); } return; } vector<vector<int>> combine(int n, int k) { track_back(n,k,0); return result; } };
