Given a collection of integers that might contain duplicates, nums, return all possible subsets (the power set).
Note: The solution set must not contain duplicate subsets.
- Example:
- Input: [1,2,2]
- Output:
- [
- [2],
- [1],
- [1,2,2],
- [2,2],
- [1,2],
- []
- ]
- Solution 1
- class Solution {
- public List<List<Integer>> subsetsWithDup(int[] nums) {
- List<List<Integer>> res = new ArrayList<>();
- if (nums == null || nums.length == 0) {
- return res;
- }
- Arrays.sort(nums);
- helper(res, new ArrayList<>(), nums, 0);
- return res;
- }
- private void helper(List<List<Integer>> res, List<Integer> list, int[] nums, int index) {
- res.add(new ArrayList<>(list));
- for (int i = index; i <nums.length; i++) {
- if (i> index && nums[i] == nums[i - 1]) {
- continue;
- }
- list.add(nums[i]);
- // use i not index b/c index smaller than i
- helper(res, list, nums, i + 1);
- list.remove(list.size() - 1);
- }
- }
- }
- class Solution {
- public List<List<Integer>> subsetsWithDup(int[] nums) {
- List<List<Integer>> result = new ArrayList<>();
- if (nums == null) {
- return result;
- }
- List<Integer> list = new ArrayList<>();
- Arrays.sort(nums);
- helper(nums, list, 0, result);
- return result;
- }
- private void helper(int[] nums, List<Integer> list, int level, List<List<Integer>> result) {
- if (level == nums.length) {
- result.add(new ArrayList<>(list));
- return;
- }
- // need to add first, skip index and then remove
- list.add(nums[level]);
- helper(nums, list, level + 1, result);
- list.remove(list.size() - 1);
- while (level + 1 < nums.length && nums[level] == nums[level + 1]) {
- level += 1;
- }
- helper(nums, list, level + 1, result);
- }
- }
- [LC] 90. Subsets II
来源: http://www.bubuko.com/infodetail-3424390.html