/
Solution.java
63 lines (59 loc) · 2.05 KB
/
Solution.java
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
/**
* Time : O(2^n); Space: O(2^n)
* @tag : Array; Backtracking
* @by : Steven Cooks
* @date: Jun 13, 2015
************************************************************************
* Given a collection of integers that might contain duplicates, nums,
* 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 nums = [1,2,2], a solution is:
* [ [2], [1], [1,2,2], [2,2], [1,2], [] ]
*
************************************************************************
* {@link https://leetcode.com/problems/subsets-ii/ }
*/
package _090_SubsetsII;
import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;
/**
* see test {@link _090_SubsetsII.SolutionTest } , see recursive solution
* {@link _090_SubsetsII.SolutionRecursive }
*/
public class Solution {
public List<List<Integer>> subsetsWithDup(int[] nums) {
List<List<Integer>> result = new ArrayList<>();
Arrays.sort(nums);
// empty list is subset of any list
result.add(new ArrayList<>());
// enlarged size by last non-repeated number
int k = 0;
for (int i = 0; i < nums.length; i++) {
int num = nums[i];
int size = result.size();
int start = 0;
if (i == 0 || num != nums[i - 1]) {
k = size;
} else {
// for repeating number
start = size - k;
}
// for a non-repeated number, a new number will double the size of current result
// by adding this number to each of existing subset;
// for a repeated number, this repeated number will only change
// those "new subsets" created by last number in the loop
for (int j = start; j < size; j++) {
List<Integer> list = new ArrayList<>(result.get(j));
list.add(num);
result.add(list);
}
}
return result;
}
}