题目

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],

]

分析

数学领域的组合问题，求1~n中k个数的组合问题。

看到题目的条件反射就是暴力法依次列举解决问题，实际上这条道路应该是行不通的，即便是得到正确结果，时间复杂度也会很高。

仔细思考，这道题目可以用动态规划的思想解决：

1~n中k个数的所有组合一定是由两部分组成：

1. 第一部分，求（1~n-1）中k-1个数的所有组合，然后每个组合中加入元素n；
2. 第二部分，求（1~n-1）中k个数的所有组合；

上述两部分合并便可以得到1~n中k个数的所有组合。

算法设计需要注意几个问题，避免不必要的bug：

1. 判断 n<=0 时，组合为空
2. 判断 n<k 时（也就包括了 k<=0 的情况），组合均为空
3. 判断 k==1 时， 1−n 每个元素为一个组合，返回 n 个组合
4. 判断 n==k 时，此时只有一个组合，包括元素 1−n

AC代码

class Solution {

public:

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

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

            return vector<vector<int>>();

        //保存结果

        vector<vector<int>> ret;

        if (k == 1)

        {

            for (int i = 1; i <= n; i++)

            {

                vector<int> v(1,i);

                ret.push_back(v);

            }//for

            return ret;

        }//if

        if (n == k)

        {

            vector<int> v;

            for (int i = 1; i <= n; i++)

            {

                v.push_back(i);

            }//for

            ret.push_back(v);

            return ret;

        }//if

        else{

            //由两部分组成，第一部分为 1~n-1 中k-1个数的组合，每个组合加入元素n

            vector<vector<int>> tmp = combine(n - 1, k - 1);

            int len = tmp.size();

            for (int i = 0; i < len; i++)

            {

                tmp[i].push_back(n);

                ret.push_back(tmp[i]);

            }//for

            //第二部分，1~n-1中 k个数的组合，两部分合并得到最终结果

            tmp = combine(n - 1, k);

            len = tmp.size();

            for (int i = 0; i < len; i++)

            {

                ret.push_back(tmp[i]);

            }//for

            return ret;

        }//else

    }

};

GitHub测试程序源码