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],]
class Solution {private: vector> result; vector a ; public: void findResult(int n, int k, int num,int start ) { if(num == k) { result.push_back(a); return; } for(int i = start; i <= n; i++) { a[num] = i; findResult( n, k, num+1, i+1); } } vector > combine(int n, int k) { // Start typing your C/C++ solution below // DO NOT write int main() function a.resize(k); result.clear(); findResult( n, k, 0, 1) ; return result; }};
重写后:
//Combinationsclass Solution {public: void DFS(int n, int start,int k, vector &ans){ if(ans.size() == k){ res.push_back(ans); return; } for(int i = start; i <= n; i++) { ans.push_back(i); DFS(n, i+1, k, ans); ans.pop_back(); } } vector> combine(int n, int k) { // Start typing your C/C++ solution below // DO NOT write int main() function res.clear(); vector ans; DFS(n, 1, k, ans); return res; }private: vector > res;};