1 class Solution {

 2

 3 private:

 4     vector<vector<int>> res;

 5

 6     // 求解C(n,k)，当前已经找到的组合存在c中，从start开始搜索新元素

 7     void generateCombinations(int n , int k , int start, vector<int> &c){

 8

 9         if( c.size() == k ){

10             res.push_back(c);

11             return;

12         }

13

14         for( int i = start ; i <= n ; i ++ ){

15             c.push_back(i);

16             generateCombinations(n, k, i + 1, c);

17             // 回溯

18             c.pop_back();

19         }

20         return;

21     }

22 public:

23     vector<vector<int>> combine(int n, int k) {

24          res.clear();

25         if( n <= 0 || k <= 0 || k > n)

26             return res;

27         vector<int> c;

28         generateCombinations(n, k, 1, c);

29

30         return res;

31     }

32 };

 1 class Solution {

 2

 3 private:

 4     vector<vector<int>> res;

 5

 6     // 求解C(n,k)，当前已经找到的组合存在c中，从start开始搜索新元素

 7     void generateCombinations(int n , int k , int start, vector<int> &c){

 8

 9         if( c.size() == k ){

10             res.push_back(c);

11             return;

12         }

13

14         // 进入函数时还有k-c.size()个空位

15         // 所以[i...n]中至少要有k-c.size()个元素

16         // 故i最多为 n - (k-c.size()) + 1

17         for( int i = start ; i <= n - (k-c.size()) + 1 ; i ++ ){

18             c.push_back(i);

19             generateCombinations(n, k, i + 1, c);

20             // 回溯

21             c.pop_back();

22         }

23         return;

24     }

25 public:

26     vector<vector<int>> combine(int n, int k) {

27          res.clear();

28         if( n <= 0 || k <= 0 || k > n)

29             return res;

30         vector<int> c;

31         generateCombinations(n, k, 1, c);

32

33         return res;

34     }

35 };