leetcode 77:Combinations
885 ワード
タイトル:
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:
遡及する思想は、比較的簡単で、前に似たような考え方がたくさんあって、参考にすることができます.
次のようになります.
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],
]
考え方:遡及する思想は、比較的簡単で、前に似たような考え方がたくさんあって、参考にすることができます.
次のようになります.
class Solution {
public:
vector<vector<int>> combine(int n, int k) {
vector<vector<int>> result;
vector<int> temp;
back(result,temp,n,k,0,1);
return result;
}
void back(vector<vector<int>> &result,vector<int> &temp, int n, int k, int count,int index)
{
if (count == k)
{
result.push_back(temp);
return;
}
if (index > n) return;
for (int i = index; i <= n; i++)
{
temp.push_back(i);
back(result,temp,n,k,count+1,i+1);
temp.pop_back();
}
}
};