題意
給定一組候選數字 candidates 和一個目標數字 target，找出 candidates 中所有可以使數字和為 target 的組合。
其中 candidates 中的每個數字在組合中只能使用 一次。
此外，解集合不能包含重複的組合。
約束條件
- 1≤candidates.length≤100
- 1≤candidates[i]≤50
- 1≤target≤30
思路：回溯(Backtracking)
要找出所有可能的組合，可以使用 回溯(Backtracking) 來解決。回溯有兩種考慮方式，分別是考慮當前元素選或不選、或考慮下一個選擇的元素，這裡使用後者。
但需要注意，題目要求不能包含重複的組合，舉例來說，若 candidates=[1,1],target=1，則選擇第一個 1 後和選擇第二個 1 後被視為重複的組合。為此我們需要在選擇的時候進行限制，使得若選擇 1 個 x ，則選擇的必須是第一個 x；若選擇 2 個 x，則選擇的必須是前兩個 x。
為了完成上述的限制，可以將 candidates 進行排序，使得相同元素的位置相鄰，如此便可以在回溯過程中跳過重複的元素；此外，如果當前累積的和已經超過目標值時，由於排序後確保後面的值都比前面的值大，因此可以及時終止當前的路徑進行 剪枝(Pruning) 。
在遞迴的每一層中，若有多個相同的元素 x ，則沒選當前層可以考慮到的第一個 x 時，也不能選第二個之後的 x 。假設當前層可以選擇的元素的下標 j∈[i,n)，則當 j>i 且 candidates[j]=candidates[j−1] 時，則不需要再考慮 j 。
複雜度分析
- 時間複雜度：O(n×2n)
- 每個元素都有選和不選兩種選擇，總共有 n 個元素，因此總共有 2n 種選擇。
- 註：有些題解會寫 O(n!) ，但其實可以用更逼近的方式分析。
- 而每種選擇都需要 O(n) 的時間來複製路徑。
- 空間複雜度：O(n)，不計算答案的空間。
- 遞迴的深度最多為 n 層，且使用 O(n) 的空間來儲存路徑。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
| class Solution:
def combinationSum2(self, candidates: List[int], target: int) -> List[List[int]]:
n = len(candidates)
candidates.sort()
ans = []
path = []
def dfs(i: int, s: int):
if s == target:
ans.append(path[:])
return
for j in range(i, n):
if j > i and candidates[j] == candidates[j - 1]:
continue
if s + candidates[j] > target:
break
path.append(candidates[j])
dfs(j + 1, s + candidates[j])
path.pop()
dfs(0, 0)
return ans
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
| class Solution {
public:
vector<vector<int>> combinationSum2(vector<int>& candidates, int target) {
int n = candidates.size();
sort(candidates.begin(), candidates.end());
vector<vector<int>> ans;
vector<int> path;
function<void(int, int)> dfs = [&](int i, int s) {
if (s == target) {
ans.push_back(path);
return;
}
for (int j = i; j < n; ++j) {
if (j > i && candidates[j] == candidates[j - 1]) continue;
if (s + candidates[j] > target) break;
path.push_back(candidates[j]);
dfs(j + 1, s + candidates[j]);
path.pop_back();
}
};
dfs(0, 0);
return ans;
}
};
|
寫在最後
masterpiece, best quality, high quality, extremely detailed CG unity 8k wallpaper, extremely detailed, High Detail, vibrant, colors, backlight, bright, soft lighting, dreamy atmosphere, orange tone, (1girl, solo), long hair, looking at viewer, gentle smile, bangs, black hair, brown eyes, standing, sleeveless, indoors, blunt bangs, bag, sleeveless dress, handbag, dress, (orange dress), in the library, library, bookshelves, warm light filtering through windows, cozy ambiance, soft shadows, detailed background, vintage decor, scattered books, wooden furniture
感覺寫的不是很清楚，等下次遇到再來看我自己能不能看得懂這篇題解XD
