[FollowUp] Combinations 组合项
组合
2023-09-11 14:21:39 时间
这是 Combinations 组合项 的延伸,在这里,我们允许不同的顺序出现,那么新的题目要求如下:
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:
[
[1,2],
[1,3],
[1,4],
[2,1],
[2,3],
[2,4],
[3,1],
[3,2],
[3,4],
[4,1],
[4,2],
[4,3],
]
这题的解法其实只是在原题 Combinations 组合项 的基础上做很小的改动即可,这里我们为了避免重复项,引入了visited数字来标记某个数组是否出现过,然后就是递归中的循环不是从level开始,改为每次从0开始,这样就能把所有不同的排列方式都找出来,代码如下:
class Solution { public: vector<vector<int> > combine(int n, int k) { vector<vector<int> > res; vector<int> out; vector<int> visited(n, 0); combineDFS(n, k, 0, visited, out, res); return res; } void combineDFS(int n, int k, int level, vector<int> &visited, vector<int> &out, vector<vector<int> > &res) { if (out.size() == k) res.push_back(out); else { for (int i = 0; i < n; ++i) { if (visited[i] == 0) { visited[i] = 1; out.push_back(i + 1); combineDFS(n, k, level + 1, visited, out, res); out.pop_back(); visited[i] = 0; } } } } };
相关文章
- React-组合模式
- 组合优于继承 Composition over inheritance
- 给定三个数a,b,c,请问满足以下3个条件的xy组合数有多少个?
- 所有在Linux系统下 arp -d $ip 命令只能清除一个IP地址的对应MAC地址缓存,可以使用组合命令操作。
- 设计模式java——组合模式
- HDU 6397 Character Encoding (组合数学 + 容斥)
- UVa 11645 Bits (暴力+组合数学)
- UVa 12034 Race (递推+组合数学)
- 复合索引(组合索引)
- SwiftUI 代码速查之 09 NavigationView和switch组合 编程控制界面显示
- UML中关联,组合与聚合等关系的辨析
- Python字符串操作之字符串分割与组合
- 10、ReactJs基础知识10--组件组合 vs 继承
- 【loj6261】一个人的高三楼 NTT+组合数学
- 【bzoj4710】[Jsoi2011]分特产 容斥原理+组合数学