216. Combination Sum III
找到所有有效的 k 個數字組合，使得它們的和等於 n，並且以下條件成立：只使用數字 1 到 9。
每個數字最多使用一次。
返回所有可能的有效組合的列表。列表中不應包含相同的組合，並且組合可以按任意順序返回。
範例：
輸入：k = 3, n = 7 輸出：[[1,2,4]] 解釋： 1 + 2 + 4 = 7 沒有其他有效組合。
Python
class Solution:
def combinationSum3(self, k: int, n: int) -> List[List[int]]:
def backtrack(start, remaining_k, remaining_n, path):
if remaining_k == 0 and remaining_n == 0:
result.append(path)
return
if remaining_k < 0 or remaining_n < 0:
return
for i in range(start, 10):
backtrack(i + 1, remaining_k - 1, remaining_n - i, path + [i])
result = []
backtrack(1, k, n, [])
return result
16.40MB, 40ms
C++
class Solution {
public:
vector<vector<int>> combinationSum3(int k, int n) {
vector<vector<int>> result;
vector<int> combination;
backtrack(1, k, n, combination, result);
return result;
}
private:
void backtrack(int start, int k, int n, vector<int>& combination, vector<vector<int>>& result) {
// Base case: if the combination is valid
if (k == 0 && n == 0) {
result.push_back(combination);
return;
}
// Base case: if the combination is invalid
if (k < 0 || n < 0) {
return;
}
// Iterate through the numbers from 'start' to '9'
for (int i = start; i <= 9; ++i) {
// Add the current number to the combination
combination.push_back(i);
// Recur with the updated values
backtrack(i + 1, k - 1, n - i, combination, result);
// Remove the current number to backtrack
combination.pop_back();
}
}
};
8.00MB, 3ms
Javascript
/**
* @param {number} k
* @param {number} n
* @return {number[][]}
*/
var combinationSum3 = function(k, n) {
const result = [];
const backtrack = (start, remainingK, remainingN, path) => {
if (remainingK === 0 && remainingN === 0) {
result.push([...path]);
return;
}
if (remainingK < 0 || remainingN < 0) {
return;
}
for (let i = start; i <= 9; i++) {
path.push(i);
backtrack(i + 1, remainingK - 1, remainingN - i, path);
path.pop();
}
};
backtrack(1, k, n, []);
return result;
};
49.21MB, 55ms
