LeetCode Subsets II

Given a collection of integers that might contain duplicates, S, return all possible subsets.

Note:

Elements in a subset must be in non-descending order.
The solution set must not contain duplicate subsets.

For example,
If S = [1,2,2], a solution is:

[
  [2],
  [1],
  [1,2,2],
  [2,2],
  [1,2],
  []
]

每一次都在前一次的基础上添加新的数就行了。

 1 public class Solution {
 2     public List<List<Integer>> subsetsWithDup(int[] num) {
 3         List<List<Integer>> result = new ArrayList<List<Integer>>();
 4         result.add(new ArrayList<Integer>());
 5         if (num.length == 0) {
 6             return result;
 7         }
 8         Arrays.sort(num);
 9         for (int i = 0; i < num.length; i++) {
10             List<List<Integer>> current = new ArrayList<List<Integer>>(result);
11             for (List<Integer> list : result) {
12                 List<Integer> newlist = new ArrayList<Integer>(list);
13                 newlist.add(num[i]);
14                 if (!current.contains(newlist)) {
15                     current.add(newlist);
16                 }
17             }
18             result = current;
19         }
20         return result;
21     }
22 }