[leetnode] #78 SubSets

Title - #78 SubSets

Level - Medium

Description - 題目主要是給一個字串 S = [1,2,3]，列出所有非遞減的子集合。

(補充)

這裡犯了兩個錯誤：它指的 non-decreasing 是嚴格遞增的意思。例如 [1,3,2,4] 不是嚴格遞增。

第二，若要列出僅"非遞減"的所有數列不太可能，因為所有組合是2N個。

作法(一) 遞迴

1:  Play(nil, S, ret);  
2:  Play(set, subset, ret) {  
3:   if (subset == nil) {  
4:    ret.add([]);  
5:    return;  
6:   }  
7:   for ( s in subset ){  
8:     if (set==nil || s>max(set)) {  
9:      ret.add({set+s});  
10:      Play({set + s}, {subset-s}, ret);  
11:   }  
12:  }  

作法(二) iteration

1:  subset<-nil;  
2:  for (s in S) {  
3:    s.add({s});  
4:  }  
5:  while (1) {  
6:    if (subset == nil) {  
7:     ret.add([]);  
8:     break;  
9:    }  
10:    ss <- subset.pop(0);  
11:    ret.add(ss);  
12:    for (s in {S-ss}) {  
13:     if (s > max(ss))  
14:      subset.add({ss, s});  
15:    }  
16:  }  

time complexity: O(n2)

另外，由於我是使用 java, 遇到了兩個問題網，路上暫時沒有較generic的作法。

(1) int[] 轉 List 的問題。

 tmp = new ArrayList<Integer>();              
 for (int i:s) {  
   tmp.add(new Integer(i));  
 }  

(2) int[] 長度增加的問題

 int[] t = new int[s.length+1];  
 t = Arrays.copyOf(s, s.length+1);  
 t[s.length] = S[j];