博文中会简要介绍Leetcode P0077题目分析及解题思路。
“Combinations”是一道比较简单的深度优先搜索的问题，用回溯法的思路就可以解决。
Given two integers n and k, return all possible combinations of k numbers out of 1 … n.
You may return the answer in any order.
以下是Java的题解代码实现。
class Solution {
public List<List<Integer>> combine(int n, int k) {
if (k == 0)
return this.combinations;
this.dfs(1, k, n, new ArrayList<>());
return this.combinations;
}
private List<List<Integer>> combinations = new ArrayList<>();
private void dfs(int start, int k, int n, List<Integer> sequence) {
if (k <= 0) {
combinations.add(new ArrayList<>(sequence));
return;
}
for (int itr=start; itr<=n; ++itr) {
sequence.add(itr);
this.dfs(itr+1, k-1, n, sequence);
sequence.remove(sequence.size()-1);
}
}
}
以下是C++的题解代码实现。
class Solution {
public:
vector<vector<int>> combine(int n, int k) {
if (k == 0)
return this->combinations;
vector<int> sequence;
this->Dfs(1, n, k, sequence);
return this->combinations;
}
private:
vector<vector<int>> combinations;
void Dfs(const int start, const int n, int k, vector<int> &sequence) {
if (k <= 0) {
this->combinations.push_back(vector<int>(sequence));
return;
}
for (int itr=start; itr<=n; ++itr) {
sequence.push_back(itr);
this->Dfs(itr+1, n, k-1, sequence);
sequence.pop_back();
}
}
};