欢迎访问LeetCode题解合集
题目描述
给定两个整数 n 和 k,返回 1 … n 中所有可能的 k 个数的组合。
示例:
输入: n = 4, k = 2
输出:
[
[2,4],
[3,4],
[2,3],
[1,2],
[1,3],
[1,4],
]
题解:
法一:
回溯 + 剪枝。
dfs( pos, rest, n )
,表示当前从 pos
位置开始,还剩 rest
个元素待选择,n
表示可选元素的范围。
剪枝:如果 pos + rest > n
,说明此时把 pos~n-1
的元素都选择了,还不够 rest
,可以直接返回( pos
从 0
开始,既代表位置,也代表值)。
时间复杂度:$O(\binom{n}{k} \times k)$
额外空间复杂度:$O(n + k)$
写法有两种,一种是循环写法:
class Solution {
public:
vector<vector<int>> ret;
vector<int> path;
void dfs( int p, int rest, int n ) {
if ( !rest ) {
ret.push_back( path );
return;
}
for ( int i = p; i + rest <= n; ++i ) {
path.push_back( i + 1 );
dfs( i + 1, rest - 1, n );
path.pop_back();
}
}
vector<vector<int>> combine(int n, int k) {
if ( k > n ) return {};
dfs( 0, k, n );
return ret;
}
};
/*
时间:4ms,击败:99.89%
内存:9.6MB,击败:74.38%
*/
另外一种写法就是:选 与 不选,两次 dfs
class Solution {
public:
vector<vector<int>> ret;
vector<int> path;
void dfs( int p, int rest, int n ) {
if ( !rest ) {
ret.push_back( path );
return;
}
if( p >= n || p + rest > n ) return;
path.push_back( p + 1 );
dfs( p + 1, rest - 1, n );
path.pop_back();
dfs( p + 1, rest, n );
}
vector<vector<int>> combine(int n, int k) {
if ( k > n ) return {};
dfs( 0, k, n );
return ret;
}
};
/*
时间:8ms,击败:98.80%
内存:18.3MB,击败:18.46%
*/
法二:
考虑二进制枚举子集,如果枚举所有状态,时间复杂:$O(n * 2^n)$
class Solution {
public:
vector<vector<int>> ret;
vector<int> path;
vector<vector<int>> combine(int n, int k) {
if ( k > n ) return {};
for ( int i = (1 << k) - 1; i < (1 << n); ++i ) {
path.clear();
for ( int j = 0; j < n; ++j ) {
if ( i >> j & 1 ) {
path.emplace_back( j + 1 );
if ( path.size() > k ) break;
}
}
if ( path.size() == k ) ret.emplace_back( path );
}
return ret;
}
};
/*
时间:160ms,击败:10.19%
内存:9.5MB,击败:74.82%
*/
其实,这种无脑枚举中有很多状态我们不需要考虑。。。
换个角度考虑:假设我们用长度为 n
的二进制数表示 1~n
这 n
个数每个数的状态, 1
表示该数被选择, 0
表示该数未被选。那么题目就变成在长度为 n
的二进制数中,找出所有二进制表示中有 k
位为 1
的二进制数。这样我们就没必要去考虑那些无用的状态(1
的个数不等于 k
)。
这里我们从最小的数开始,从小到大来考虑:
比如 n = 6
,k = 4
,题目变成从 x = 001111
开始,不停的查找最小的比 x
大且二进制表示中 1
的个数与 x
相同的数。
假设 N = 78
,二进制表示为 1001110
,最小的比 N
大且二进制表示中 1
与 N
相同的数,也就是 83
,其二进制表示为 1010011
。
我们来观察 78
变成 83
的规律:
78: 1 0 0 1 1 1 0
83: 1 0 1 0 0 1 1
只需要对 78
的二进制表示中最右边连续的 1
串进行操作!
具体来说就是:将最右边连续的 1
串中最左边的 1
向左 移动 一位,其它的 1
移动 到最右边。
这样既可以保证二进制表示中 1
的个数保持不变,且保证了新得到的数比原来的数大,且是最小的:
但具体操作时,不是对这些二进制位进行移动,而是通过位操作来达到同样的目的。
首先是 int x = N & (-N)
,找到 N
的二进制表示中最右边的这个 1
(这个 1
必定是二进制表示中最右边连续的 1
串的开始)。
接下来考虑 int t = N + x
,该语句将连续的 1
串中最左边的 1
向左移动一位.但是这操作也让连续的 1
串中其它的 1
丢失了。
接下来就是考虑将丢失的 1
补上,并移动到最右边。
首先,需要知道需要补多少个 1
,由上面可知,需要补得 1
的个数为 N
的二进制表示中最右边的连续的 1
串中 1
的个数减一。如何通过位操作来得到呢?可以通过 N^t
得到,N^t
的二进制表示只包含 一个连续的 1
串,并且 1
的个数正好等于 N
的二进制表示中最右边连续的 1
串中 1
的个数加一:
所以 N^t
中的 1
的个数比我们需要补得 1
的个数多 2
,并且 N^t
中最低位的 1
与 x
中的那个 1
对应,这样我们通过:((N^t)/x)>>2
,得到要补的 1
的个数和其位置:
最后,t | ((N^t)/x) >> 2
就可以得到所求的数字了。
这种写法还需要遍历 N
的二进制表示中每一位 1
的位置,预处理一下就行。
注意:二进制变化的上界是 11110000......
。
时间复杂度:$O(\binom{n}{k} \times k)$
额外空间复杂度:$O(n + k)$
class Solution {
public:
vector<vector<int>> ret;
vector<int> path;
vector<vector<int>> combine(int n, int k) {
if ( k > n ) return {};
int gap = (1 << n) - (1 << (n - k));
int now = (1 << k) - 1;
unordered_map<int, int> one_pos;
path = vector<int>(k);
for ( int i = 0; i < n; ++i ) one_pos[1 << i] = i;
int idx = 0, lowbit;
while ( now <= gap ) {
int tmp = now;
idx = 0;
while ( tmp ) {
lowbit = tmp & -tmp;
path[idx++] = one_pos[lowbit] + 1;
tmp ^= lowbit;
}
ret.emplace_back( path );
int x = now & -now;
int t = now + x;
now = ((now ^ t) >> one_pos[x] >> 2) | t;
}
return ret;
}
};
/*
时间:8ms,击败:98.80%
内存:9.7MB,击败:71.34%
*/