赞
踩
77. 组合
今天就做一题,回溯剪枝。我的理解就是把多层for循环放到递归里实现,通过剪枝来减少递归次数。遍历顺序类似N叉树的遍历。
class Solution { public: //定义全局变量更方便 vector<int> path; vector<vector<int>> res; void backtracking(int n, int k, int startIndex){ if (path.size() == k){ res.push_back(path); return; } // 未剪枝 // for (int i = startIndex;i <= n; i++){ // path.push_back(i); // backtracking(n, k, i + 1); // path.pop_back(); // } // 剪枝 for (int i = startIndex; i <= n - (k - path.size()) + 1; i++){ path.push_back(i); backtracking(n, k, i + 1); path.pop_back(); } } vector<vector<int>> combine(int n, int k) { backtracking(n, k, 1); return res; } };
Copyright © 2003-2013 www.wpsshop.cn 版权所有,并保留所有权利。