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

?

思路：有點像0-1背包問題， 對于從1-n的每一個數(shù)字都可以選擇放入答案 和不放入答案。 當長度達到k時就是一個符合條件的解。

遞歸的代碼，AC了。只要注意狀態(tài)的還原就好。

#include <iostream> #include <vector> #include <algorithm> #include <queue> #include <stack> using namespace std;class Solution { public:vector<vector<int> > combine(int n, int k) {vector<vector<int>> ans;combinepart(ans, 1, k, n);return ans;}void combinepart(vector<vector<int>> &ans, int num, int k, int n){static int i = 0;static vector<int> partans;if(num - 1 > n || partans.size() + (n - num + 2) < k) return; //數(shù)字超過了n 或者即使后面數(shù)字全部壓入長度也不夠的時候 直接返回 避免不必要的計算if(i == k){ans.push_back(partans);return;}partans.push_back(num); //放入numi++;combinepart(ans, num + 1, k, n);partans.pop_back();i--;combinepart(ans, num + 1, k, n);//不放入num } };int main() {Solution s;vector<vector<int>> ans = s.combine(3,3);return 0; }

?

網(wǎng)上有非遞歸的代碼，可是我好困，懶得看... 速度都差不多的，因為我的遞歸截枝了，沒有多余的操作。

class Solution { public:vector<vector<int> > combine(int n, int k) {vector<vector<int> >ret;if(k>n||k<=0)return ret;for(int i=1;i<=n-k+1;i++){ret.push_back(vector<int>(1,i));}for(int i=2;i<=k;i++){int num=ret.size();for(int j=0;j<num;j++){int last=ret[j].back();vector<int> pretmp=ret[j];ret[j].push_back(last+1);for(int p=last+2;p+k-i<=n;p++){vector<int> tmp=pretmp;tmp.push_back(p);ret.push_back(tmp);}}}return ret; } };

?

轉(zhuǎn)載于:https://www.cnblogs.com/dplearning/p/4237673.html

總結(jié)

以上是生活随笔為你收集整理的【leetcode】Combinations (middle)的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯，歡迎將生活随笔推薦給好友。