HackMD
題目描述
Given two integers n and k, return all possible combinations of k numbers chosen from the range [1, n].
You may return the answer in any order.
範例
Example 1:
Input: n = 4, k = 2
Output: [[1,2],[1,3],[1,4],[2,3],[2,4],[3,4]]
Explanation: There are 4 choose 2 = 6 total combinations.
Note that combinations are unordered, i.e., [1,2] and [2,1] are considered to be the same combination.
Example 2:
Input: n = 1, k = 1
Output: [[1]]
Explanation: There is 1 choose 1 = 1 total combination.
Constraints:
- 1 <=
n<= 201 <= n <= 20
1 <= k <= n - 1 <= k <= n
解答
C++
class Solution {
public:
vector<vector<int>> combine(int n, int k) {
vector<int> subAns;
vector<vector<int>> ans;
backtrack(n, k, 1, subAns, ans);
return ans;
}
void backtrack(int n, int k, int first, vector<int>& subAns, vector<vector<int>>& ans) {
if (subAns.size() == k) {
ans.push_back(subAns);
return ;
}
for (int i = first; i <= n; i ++) {
subAns.push_back(i);
backtrack(n, k, i + 1, subAns, ans);
subAns.pop_back();
}
}
};
Jerry Wu1 August, 2023
Python
內建作弊一下XD
class Solution:
def combine(self, n: int, k: int) -> List[List[int]]:
return list(combinations(range(1, n + 1), k))
class Solution:
def combine(self, n: int, k: int) -> List[List[int]]:
res = []
def backtrack(i, arr):
if len(arr) == k:
res.append(arr.copy())
return
for i in range(i, n + 1):
arr.append(i)
backtrack(i + 1, arr)
arr.pop()
backtrack(1, [])
return res
Ron ChenTue, Aug 1, 2023
TypeScript
function combine(n: number, k: number): number[][] {
const result: number[][] = [];
const candidate: number[] = [];
const backtrack = (start: number) => {
if (candidate.length === k) {
result.push([...candidate]);
return;
}
for (let i = start; i <= n; i++) {
candidate.push(i); // 將數字 i 加入候選解
backtrack(i + 1); // 遞迴呼叫下一個數字
candidate.pop(); // 回溯：移除候選解的最後一個數字
}
};
backtrack(1); // 從 1 開始遞迴
return result;
}
SheepTue, Aug 1, 2023
