Leetcode典型题解答和分析、归纳和汇总——T77（组合）

题目描述：

给定两个整数n和k，返回1...n中所有可能的k个数组合

题目解析：

本题考查全排列的算法使用。最常用的就是剪枝的回溯算法。

编程实现：

class Solution{
    public：
     vector<vector<int>> res;  

      void DFS(int n, int k , int start, vector<int>& path)
      {
        if(path.size()==k)   //达到目标了
        {
            res.push_back(path);
            return;
        }

        for(int i=start; i<=n-(k-path.size())+1;i++)  //注意这个i<=n-(k-path.size())+1是经过分析剪枝后的值，排除不可能情况
        {
            path.push_back(i);
            DFS(n,k,i+1,path);
            path.pop_back();
        }
      }

    vector<vector<int>> combine(int n, int k)
    {
        if(n<=0||k<=0||k>n)  return res;
        vector<int> path;
        DFS(n,k,1,path);
        return res;
    }
};