分析：
因為要求結(jié)果集是升序排列，所以首先我們要對數(shù)組進行排序。
子集的長度可以從0到整個數(shù)組的長度。長度為n+1的子集可以由長度為n的子集再加上在之后的一個元素組成。
這里我使用了三個技巧
1。使用了一個index數(shù)組來記錄每個子集的最大索引，這樣添加新元素就很簡單。
2。使用了兩個變量start和end來記錄上一個長度的子集在結(jié)果中的起始和終止位置。
3。去重處理使用了一個last變量記錄前一次的值，它的初始值設(shè)為S[0]-1,這樣就保證了和數(shù)組的任何一個元素不同。
代碼如下：
public class Solution {
public ArrayList<ArrayList<Integer>> subsetsWithDup(
int[] S) {
Arrays.sort(S);
ArrayList<ArrayList<Integer>> result =
new ArrayList<ArrayList<Integer>>();
ArrayList<Integer> indexs =
new ArrayList<Integer>();
result.add(
new ArrayList<Integer>());
indexs.add(-1);
int slen = S.length;
int start=0,end=0;
for(
int len=1;len<=slen;++len){
int e = end;
for(
int i=start;i<=end;++i){
ArrayList<Integer> ss = result.get(i);
int index = indexs.get(i).intValue();
int last = S[0]-1;
for(
int j = index+1;j<slen;++j){
int v = S[j];
if(v!=last){
ArrayList<Integer> newss =
new ArrayList<Integer>(ss);
newss.add(v);
result.add(newss);
indexs.add(j);
++e;
last = v;
}
}
}
start = end+1;
end = e;
}
return result;
}
}