在1 - 10 中，求出 7 个数的排列组合。
出现了超时，而超时的原因是有好多重复情况，复杂度上来说，和答案的复杂度是一样的，但是答案中重复了太多了，体会下。
超时1：
class Solution {
public:
vector<vector<int> > combine(int n, int k) {
vector<vector<int> > ans;
if(n < k || n <= || k <= )
return ans;
vector<int> ansPiece;
set<int> checkExist;
for(int i = ; i <= n; i++)
{
ansPiece.clear();
ansPiece.push_back(i);
checkExist.clear();
checkExist.insert(i);
if(k > )
combine(ans,ansPiece,k,n,checkExist);
}
return ans;
}
void combine(vector<vector<int> > &ans, vector<int> &ansPiece, int &k, int &n, set<int> &checkExist)
{
if(ansPiece.size() == k)
{
vector<int> temp = ansPiece;
ans.push_back(temp);
return;
}
for(int i = ; i <=n; i++)
{
if(checkExist.find(i) == checkExist.end())
{
ansPiece.push_back(i);
checkExist.insert(i);
combine(ans,ansPiece,k,n,checkExist);
ansPiece.pop_back();
checkExist.erase(i);
}
}
}
};超时2：
class Solution {
public:
vector<vector<int> > combine(int n, int k) {
vector<vector<int> > ans;
if(n < k || n <= || k <= )
return ans;
vector<int> ansPiece;
set<int> checkExist; //记录还没有选的元素
for(int i = ; i <= n; i++)
{
checkExist.insert(i);
}
combine(ans,ansPiece,k,checkExist);
return ans;
}
void combine(vector<vector<int> > &ans, vector<int> &ansPiece, int &k, set<int> &checkExist)
{
if(ansPiece.size() == k)
{
vector<int> temp = ansPiece;
ans.push_back(temp);
return;
}
set<int>::iterator itr;
for(itr = checkExist.begin(); itr != checkExist.end(); itr++)
{
ansPiece.push_back(*itr);
set<int> check2 = checkExist;
check2.erase(*itr);
combine(ans,ansPiece,k,check2);
ansPiece.pop_back();
}
}
};正确的：（控制了顺序）
class Solution {
public:
vector<vector<int> > combine(int n, int k) {
vector<vector<int> > ans;
if(n < k || n <= || k <= )
return ans;
vector<int> ansPiece;
int start = ;
combine(ans,ansPiece, k,n, start);
return ans;
}
void combine(vector<vector<int> > &ans, vector<int> &ansPiece, int &k, int &n, int start)
{
if(ansPiece.size() == k)
{
vector<int> temp = ansPiece;
ans.push_back(temp);
return;
}
for(int i = start; i <= n; i++)
{
if(n - i + < k - ansPiece.size())
return;
ansPiece.push_back(i);
combine(ans,ansPiece,k,n,i+);
ansPiece.pop_back();
}
}
};