LC77.组合
思路1:回溯
- “叶子节点是数组的最后一个元素”类型的回溯模板题
两种回溯办法:第一种,选择当前位置或者不不选择当前位置;第二种,遍历数组进行回溯
代码1:
数组的最后一个元素当作叶子节点
class Solution {
public:
void backTrace(vector<vector<int>>& all_comb, vector<int>& cur_comb, int cur_sub, int n, int k) {
if (cur_comb.size() == k) {
all_comb.push_back(cur_comb);
return;
}
if (cur_sub == n + 1) {
return;
}
for (int i = cur_sub; i <= n; i++) {
cur_comb.push_back(i);
backTrace(all_comb, cur_comb, i + 1, n, k);
cur_comb.pop_back();
}
}
vector<vector<int>> combine(int n, int k) {
vector<vector<int>> all_comb;
vector<int> cur_comb;
backTrace(all_comb, cur_comb, 1, n, k);
return all_comb;
}
};
选择当前位置或者不选
class Solution {
public:
void dfs(int index, int k, int n, vector<vector<int>>& res, vector<int>& nums) {
if (nums.size() == k) {
res.push_back(nums);
return ;
}
if (nums.size() + (n - index) < k) {
return;
}
// 选择当前位置
nums.push_back(index + 1);
dfs(index + 1, k, n, res, nums);
nums.pop_back();
// 不选当前位置
dfs(index + 1, k ,n, res, nums);
}
vector<vector<int>> combine(int n, int k) {
vector<vector<int>> res;
vector<int> nums;
dfs(0, k, n, res, nums);
return res;
}
};
思路2:二进制暴力枚举
- 对
situation
进行枚举
// n == 2
// S 最大取到 (2 ^ n) - 1
// 00 01 10 11 (100取不到)
for (int S = 0; S < (1 << n); S++)
- 从右往左读取位置(低位为1)
// 如果第i低位是1,表示选取这个位置
if (S & (1 << i))
代码2:
class Solution {
public:
int getBinNum(int num) {
int cnt = 0;
for (int i = 0; i < 20; i++) {
if (num & 1) {
cnt += 1;
}
num >>= 1;
}
return cnt;
}
vector<vector<int>> combine(int n, int k) {
// n == 2
// S 最大取到 (2 ^ n) - 1
// 00 01 10 11 (100取不到)
vector<vector<int>> ans;
for (int S = 0; S < (1 << n); S++) {
if (getBinNum(S) == k) {
vector<int> cur_s;
for (int i = 0; i < n; i++) {
if (S & (1 << i)) {
cur_s.push_back(i + 1);
}
}
ans.push_back(cur_s);
}
}
return ans;
}
};