[LeetCode] 77. Combinations

轉自LeetCode

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:

[
  [2,4],
  [3,4],
  [2,3],
  [1,2],
  [1,3],
  [1,4],
]

<Solution>

這題是要求幾取幾的問題，例如題目的例子就是 4 取 2 會有哪些組合

這種組合性的問題，很直覺會想到 DFS 的方式

因為題目有指明每個組合的長度，所以可以先準備好長度 k 的 vector，省掉 push_back 和 pop_back 的時間

code 如下
c++

	class Solution {
	private:
	vector<vector<int>> ans;
	public:
	vector<vector<int>> combine(int n, int k) {
	if(n < k || k == 0) {
	return ans;
	}
	vector<int> out(k, 0);
	dfs(1, 0, k, n, out);
	return ans;
	}
	void dfs(const int &start, const int &len, const int &targetLen, const int &n, vector<int> &out) {
	//> found an answer
	if(len == targetLen) {
	ans.push_back(out);
	return;
	}
	//> combination
	for(int i = start; i <= n; i++) {
	out[len] = i;
	dfs(i+1, len+1, targetLen, n, out);
	}
	}
	};

view raw findCombination_1.cpp hosted with ❤ by GitHub

kotlin

	class Solution {
	private val ans = mutableListOf<List<Int>>()
	fun combine(n: Int, k: Int): List<List<Int>> {
	dfs(1, n, k, emptyList())
	return ans
	}
	fun dfs(start: Int, end: Int, targetLen: Int, cmb: List<Int>) {
	if(cmb.size == targetLen) {
	ans.add(cmb)
	return
	}
	for(i in start..end) {
	dfs(i+1, end, targetLen, cmb+listOf(i))
	}
	}
	}

view raw combinations.kt hosted with ❤ by GitHub

這題還有 iterative 的解法(參考資料)

特別說明一下 while 迴圈裡面有個檢查是 out[0] <= (n - k + 1)

這是因為每次都是小的數往上找組合

而小的數是有上限的，不然數字會不夠用

例如 n = 5, k = 3，則 out[0] 的上限會是 5 - 3 + 1 = 3

如果 out[0] = 4，那麼只剩下 5 還可以用，永遠都不可能找到三個數的組合

code 如下
c++

	class Solution {
	private:
	vector<vector<int>> ans;
	public:
	vector<vector<int>> combine(int n, int k) {
	if(n < k || k == 0) {
	return ans;
	}
	vector<int> out(k, 0);
	int index = 0;
	while(index >= 0 && out[0] <= (n-k+1)) {
	++out[index];
	if(out[index] > n) {
	//> n is the biggest number we can use
	//> go back to previous index
	--index;
	}
	else if(index == (k-1)) {
	//> record all combinations
	ans.push_back(out);
	}
	else {
	//> need to combine more numbers
	++index;
	out[index] = out[index-1];
	}
	}
	return ans;
	}
	};

view raw findCombination_2.cpp hosted with ❤ by GitHub