题目¶
Given two integers n and k, return all possible combinations of k numbers out of 1 ... n.
Example:
Input: n = 4, k = 2 Output: [ [2,4], [3,4], [2,3], [1,2], [1,3], [1,4], ]
分析¶
非常明显的用backtracking的题目。
class Solution { public: void combineHelper(int n, int k, int position, vector<int>& nums, vector<int>& chosen, vector<vector<int>>& res){ if (chosen.size()==k){ // base case res.push_back(chosen); return; }else{ for (int i= position; i<n; i++){ //choose chosen.push_back(nums[i]); // explore combineHelper(n, k, i+1, nums, chosen, res); // unchoose chosen.pop_back(); } } } vector<vector<int>> combine(int n, int k) { vector<vector<int>> res; vector<int> nums, chosen; // 初始化num为1...n for (int i=1; i< n+1; i++){ nums.push_back(i); } combineHelper(n, k, 0, nums, chosen, res); return res; } };
其实都不用nums数组,因为其nums[i]=i+1;
class Solution { public: void combineHelper(int n, int k, int position, vector<int>& chosen, vector<vector<int>>& res){ if (chosen.size()==k){ // base case res.push_back(chosen); return; }else{ for (int i= position; i<n; i++){ //choose chosen.push_back(i+1); // explore combineHelper(n, k, i+1, chosen, res); // unchoose chosen.pop_back(); } } } vector<vector<int>> combine(int n, int k) { vector<vector<int>> res; vector<int> chosen; combineHelper(n, k, 0, chosen, res); return res; } };
近期评论