首页 > 代码库 > Combinations <leetcode>

Combinations <leetcode>

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

算法:该题很简单,但是当时没想到,上网上一查才恍然大悟,就是构造一个解空间,然后用回溯解决,soeasy,不说了,上代码:

 1 class Solution { 2 public: 3     vector<vector<int>>  result; 4     vector<int>  node; 5     vector<vector<int> > combine(int n, int k) { 6          result.clear(); 7          node.resize(k); 8          doit(0,n,k,1); 9          return result;10     }11     void doit(int dep,int n,int k,int start)12     {13         if(dep==k)14         {15             result.push_back(node);16             return;17         }18         else19         {20             for(int i=start;i<=n-k+1+dep;i++)21             {22                 node[dep]=i;23                 doit(dep+1,n,k,i+1);24             }25         }26     }27 };

 

Combinations <leetcode>