[leetcode] #39 Combination Sum
Title - #39 Combination Sum
Level - Medium
Description - 題目主要是給一個字串 S = [1,2,3],一個數字target,要列出所有字串相加等於target的子集合,字串可重複出現,集合為嚴格遞增。
(補充)
這裡又發生兩次WA。一次是若找不到時回傳[]而非[[]];原先算法找無 [1,2], Target =4中 [2,2]的組合,原因是在backtracking時,si <max(subset) 時我直接break 導致 '=’ 的條件無法觸發。但是為啥 [1,1,2] OK [2,2]卻不行?不是不行而是當 (si=1)<(max=2)時就直接中斷了。(補充)
另外,若S裡頭發生重複的字串的情況下可能需要移除,只是拿到RA就不打算處理了。
這題跟昨天subset 的做法很像。
作法 (iteration)
1: Heapify(S, i, len) {
2: left = i*2, right = left+1;
3: max = i;
4: if (leftlen and S[max] < S[left]) max=left;
5: if (rightlen and S[max] < S[right]) max=right;
6: if (i<max) {
7: Swap(A, i, max);
8: Heapify(A, max, len);
9: }
10: }
11: HeapSort(S) {
12: for (int i=S.length/2;i>=0; i--) {
13: Heapify(S, i, S.length);
14: }
15: for (int i=S.length;i>=1;i--) {
16: Swap(S, 0, i-1);
17: Heapify(S, 0, i-1);
18: }
19: }
20: //step-1, O(n)
21: isAscending = True;
22: for (int i =1;i<S.length-1;i++) {
23: if (S[i] < S[j]) {
24: isAscending = False;
25: break;
26: };
27: }
28: //step-2 O(nlogn)
29: if (not isAscending)
30: HeapSort(S);
31: //step-3 initialize stack
32: T = {};
33: for (s in S) {
34: if (s < Target)
35: T.add({s});
36: elif (s == Target)
37: ret.add({s});
38: }
39: //step-4 backtracking, O(n2)
40: while (True) {
41: if (T.isEmpty()) break;
42: tmp = T.pop(0);
43: if (sum(tmp) == Target) ret.add(tmp);
44: else {
45: for (s in S) {
46: if (s > Target) break;
47: if (s < max(tmp)) continue;
48: if (sum(tmp)+s Target) T.add({tmp, s});
49: }
50: }
51: }
Comments
Post a Comment