題目很簡單就是給你兩個數 n 與 k 要你求 n 取 k 的所有組合 C(n, k) 。
EX:
n = 5, k = 4
Ans: [ [[1,2,3,4],[1,2,3,5],[1,2,4,5],[1,3,4,5],[2,3,4,5]] ]
想法:
排列組合的題目基本上很直覺的想法就是使用 recursive 的方式來列舉所有組合，因此每次直覺的作法也是這樣，但實際上會發現可以 accepted 但 rum time 很久。這邊可以注意到有個小細節可以做剪枝，舉個例子，假設我們要求 C(5, 4)，並且從 1 開始依序選取數字，每個數字可以選或不選，假設現在已經選了 1 個數字且目前已經看到 4 ，這時可以發現我們總共需要取 4 個數字而因為已經選了 1 個所以還需要再選 3 個，但這時我們已經看到 4 了，前面的數字 1~ 3 都已經決定選或不選了，這時只剩下 4, 5 可以選擇顯然就算我們兩個數字都取也不夠，因此基本上後面的分支都可以不用再進行搜索了，所以對於每個起始的數字我們其實只需要選到 n - (k - cur_size) + 1 的位置就可以了(k - cur_size 表示目前還需要選幾個數)，通過這個剪枝就可以讓 run time 提升許多。
另外還有一種數學解法，就是利用組合數學的公式 C(n , k) = C(n - 1, k - 1) + C(n - 1 , k)，其含意為 n 取 k 的方法數可以分成第 n 個數取或不取的方法數相加，所以等於在 n - 1 中取 k - 1 個數(i.e. 取第 n 個數) 加上 在 n - 1 中取 k 個數(i.e. 不取第 n 個數)的方法數相加，不過效率上還是上面的剪枝法比較快一點。
完整程式碼:
解法一 (pure dfs):
class Solution {
public:
vector<vector<int>> res;
void comb(int n, int k, vector<int>& cur) {
if (cur.size() == k) {
res.emplace_back(cur);
return;
}
int s = cur.empty()? 1 : cur.back() + 1;
for (int i = s; i <= n; i++) {
cur.emplace_back(i);
comb(n, k, cur);
cur.pop_back();
}
return;
}
vector<vector<int>> combine(int n, int k) {
vector<int> cur;
comb(n, k, cur);
return res;
}
};
解法二(dfs with prune):
class Solution {
public:
vector<vector<int>> ans;
void dfs(int n, int k, vector<int>& cur) {
if (cur.size() == k) {
ans.emplace_back(cur);
return;
}
auto s = cur.empty()? 1 : cur.back() + 1;
// prune!!!
// k - cur.size() means that the remaining number of element we need,
// so n - (k - cur.size()) + 1 is the meaningful search we need,
// for example: if n = 5, k = 4 and cur.size() = 1, we still need 4 - 1 = 3 element, but if i from start ~ 4, then next deep we only can get 5 and fail to get four element, so the search after i = 3 is meaningless.
for (int i = s; i <= n - (k - cur.size()) + 1; ++i) {
cur.emplace_back(i);
dfs(n, k, cur);
cur.pop_back();
}
}
vector<vector<int>> combine(int n, int k) {
vector<int> cur;
dfs(n, k, cur);
return ans;
}
};
解法三(mathematics):
class Solution {
public:
// based on the idea Cn,m = Cn-1,m-1 + Cn-1,m
// Cn,m equal to choose n and choose m - 1 on remaining n - 1 element and
// don't choose n and choose m on remaining n - 1 element
vector<vector<int>> combine(int n, int k) {
if (k == 0 || k == n) {
vector<vector<int>> ans;
vector<int> cur(k, 0);
for (int i = 1; i <= k; i++) {
cur[i-1] = i;
}
ans.emplace_back(cur);
return ans;
}
vector<vector<int>> ans;
// choose n
ans = combine(n - 1, k - 1);
for (auto& c : ans) {
c.emplace_back(n);
}
// don't choose n
auto tmp = combine(n - 1, k);
ans.insert(ans.end(), tmp.begin(), tmp.end());
return ans;
}
};
沒有留言:
張貼留言