建立商城网站,wordpress被扫描,个性个人网站模板,微课做动画的网站目录
力扣77. 组合
解析代码 力扣77. 组合
77. 组合
难度 中等
给定两个整数 n 和 k#xff0c;返回范围 [1, n] 中所有可能的 k 个数的组合。
你可以按 任何顺序 返回答案。
示例 1#xff1a;
输入#xff1a;n 4, k 2
输出#xff1a;
[[2,4],[3,4],[2,3],[1,…目录
力扣77. 组合
解析代码 力扣77. 组合
77. 组合
难度 中等
给定两个整数 n 和 k返回范围 [1, n] 中所有可能的 k 个数的组合。
你可以按 任何顺序 返回答案。
示例 1
输入n 4, k 2
输出
[[2,4],[3,4],[2,3],[1,2],[1,3],[1,4],
]
示例 2
输入n 1, k 1
输出[[1]]提示
1 n 201 k n
class Solution {
public:vectorvectorint combine(int n, int k) {}
}; 解析代码 题目要求我们从 1 到 n 中选择 k 个数的所有组合其中不考虑顺序。也就是说[1,2] 和 [2,1] 等价。我们需要找出所有的组合但不能重复计算相同元素的不同顺序的组合。对于选择组合我们需要进行如下流程
所有元素分别作为首位元素进行处理。在之后的位置上同理选择所有元素分别作为当前位置元素进行处理。为避免计算重复组合规定选择之后位置的元素时必须比前一个元素大这样就不会有重复的组合 [1,2] 和 [2,1] 中 [2,1] 不会出现。
class Solution {int _n, _k;vectorint path;vectorvectorint ret;
public:vectorvectorint combine(int n, int k) {_n n;_k k;dfs(1);return ret;}void dfs(int pos){if(path.size() _k){ret.push_back(path);return;}for(int i pos; i _n; i) // 剪枝{path.push_back(i);dfs(i 1);path.pop_back(); // 恢复现场}}
};
