[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:  }