回溯算法 Python:
class Solution: def combine(self, n: int, k: int): res=[] cur=[] self.recur(n,k,1,res,cur) return res def recur(self,n,k,cur_index,res,cur): if len(cur)==k: res.append(cur[:]) //注意深拷贝 return for i in range(cur_index,n+1): cur.append(i) self.recur(n,k,i+1,res,cur) cur.pop()C++:
class Solution { public: void get_combines(vector<int>& nums, vector<int>& combine, vector<vector<int>>& ans, int k, int count, int p) { if(count == k) { ans.push_back(combine); return ; } for(int i = p; i<nums.size(); ++i) { combine.push_back(nums[i]); get_combines(nums, combine, ans, k ,count + 1, i+1); combine.pop_back(); } } vector<vector<int>> combine(int n, int k) { vector<int> nums, combine; vector<vector<int>> ans; for(int i = 1; i<=n; ++i) nums.push_back(i); get_combines(nums, combine, ans ,k, 0, 0); return ans; } };