leetcode 77 组合 全排列

缘起

继续全排列之旅!!! leetcode 77 组合

分析

1
2
3
4
5
6
7
8
9
10
11
12
13
14
给定两个整数 n 和 k，返回 1 ... n 中所有可能的 k 个数的组合。

示例:

输入: n = 4, k = 2
输出:
[
  [2,4],
  [3,4],
  [2,3],
  [1,2],
  [1,3],
  [1,4],
]

显然dfs.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
class Solution {
public:
	vector<vector<int>> combine(int n, int k) {
		vector<vector<int>> ans;
		vector<int> t;
		vector<bool> v(n+1);
		dfs(ans,t,1,k,n);
		return ans;
	}

private:
	void dfs(vector<vector<int>> &ans, vector<int> t, int cur, int k, int n) // num是迄今为止当前已经有几个数了, cur是已经决定到了哪一个数的存取, 注意, 这里t采用了值传递,而不是址传递
	{
		if (t.size()==k)
		{
			ans.push_back(t);
			return;
		}
		if (t.size()+n-cur+1<k) // 就算剩下所有的数都选上, 也到不了k, 则剪枝
		{
			return;
		}
		if (cur==n+1&&t.size()==k) // 大限已到, 如果凑够了k, 就算上吧
		{
			ans.push_back(t);
			return;
		}
		dfs(ans, t, cur+1, k, n); // 不选cur这个数
		t.push_back(cur); // 选cur这个数
		dfs(ans, t, cur+1, k,n);
	}
};

ac情况

1
2
3
4
5
6
7
8
9
10
11
12
13
执行结果：
通过
显示详情
执行用时 :
152 ms
, 在所有 C++ 提交中击败了
52.62%
的用户
内存消耗 :
48.6 MB
, 在所有 C++ 提交中击败了
22.93%
的用户

真的，真的不想写 leetcode~ 写的代码太臃肿了~ 没有算法的简练~ 感觉leetcode更强调企业开发的规范~