[LeetCode] 216. Combination Sum III

轉自LeetCode

Find all possible combinations of k numbers that add up to a number n, given that only numbers from 1 to 9 can be used and each combination should be a unique set of numbers.

Example 1:

Input: k = 3, n = 7

Output:

[[1,2,4]]

Example 2:

Input: k = 3, n = 9

Output:

[[1,2,6], [1,3,5], [2,3,4]]

<Solution>

這題一樣可以用 DFS 的思考方式去解，邏輯和 Combination Sum II 比較接近

但這題有多一些條件

• 可以指定要用幾個數字拿來組合

• 可以用的數字就是 1 - 9

只要處理一下相關條件，就沒問題了

code 如下
c++

	class Solution {
	public:
	vector<vector<int>> combinationSum3(int k, int n) {
	vector<vector<int>> ans;
	if(n <= 0 || (k == 0 && n > 0)) {
	return ans;
	}
	vector<int> out;
	int candidates[] = {1,2,3,4,5,6,7,8,9};
	combineByDFS(0, k, n, candidates, out, ans);
	return ans;
	}
	void combineByDFS(const int &start, const int &size, const int &target, int *candidates, vector<int> &out, vector<vector<int>> &ans) {
	if(out.size() == size && target == 0) {
	//> need to check size and value
	ans.push_back(out);
	}
	else {
	for(int i = start; i < 9; i++) {
	if((target-candidates[i]) >= 0 && out.size() < size) {
	out.push_back(candidates[i]);
	combineByDFS(i+1, size, target-candidates[i], candidates, out, ans);
	out.pop_back();
	}
	}
	}
	}
	};

view raw combinationSum_3.cpp hosted with ❤ by GitHub

kotlin

	class Solution {
	private val ans = mutableListOf<List<Int>>()
	fun combinationSum3(k: Int, n: Int): List<List<Int>> {
	dfs(1, k, n, emptyList())
	return ans
	}
	fun dfs(start: Int, k: Int, target: Int, cmb: List<Int>) {
	if (target == 0 && cmb.size == k) {
	ans.add(cmb)
	return
	}
	for(i in start..9) {
	if(target - i >= 0) {
	dfs(i+1, k, target - i, cmb + listOf(i))
	}
	}
	}
	}

view raw combination_sum_III.kt hosted with ❤ by GitHub