# *Java* straightforward iterative solution (4ms)

• Key ideas:

• sort the array
• store obtained list up to index i (exclusive)
• for index i, skip all values equal to i and count number of skipped items. Consider all items with same value one block and process all of them at once
• It's now a simple math combination problem: from 0 to i-1, we have a list of results res, at i (after skipping duplicates), we have another list of results innerList, just add all combinations of res and innerList

For example,

e.g., nums = [1, 2, 3, 3, ...]
before i=2, we have res = [[ ], [1], [2], [1,2]]
when i=2, skip value 3 and move i to index 3, skipped indices=1
innerList = [[ ], [3], [3,3]]
add all combinations of `res` and `innerList` and the outcome becomes the new res

Code in Java:

public List<List<Integer>> subsetsWithDup(int[] nums) {
Arrays.sort(nums);
List<List<Integer>> res = new ArrayList<List<Integer>>();
List<Integer> innerList = new ArrayList<Integer>();
for(int i=0, L=nums.length; i<L; i++) {
int skipped = 0; // number of duplicate values
while(i+1<L && nums[i]==nums[i+1]) { // skip duplicates
++skipped;
++i;
}

List<List<Integer>> newList = new ArrayList<List<Integer>>(); // to store new result including i;
for(List<Integer> left : res) {
innerList = new ArrayList<Integer>();
for(int j=0; j<=skipped; j++) { // add all duplicate values
List<Integer> combined = new ArrayList<Integer>(left);