日志
Subsets II （Array，Back Tracking，Bit Manipulation）
|
题目：
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:
--
解法一：
//只要在Subset I那道题的基础上，再加上一个判断重复机制（即outerList中含不含有当前innerList）即可。
public class Solution {
public List<List<Integer>> subsetsWithDup(int[] nums) {
List<List<Integer>> outerList = new ArrayList<List<Integer>>();
if (nums == null || nums.length == 0) return outerList;
Arrays.sort(nums);
ArrayList<Integer> innerList = new ArrayList<Integer>();
helper((ArrayList<List<Integer>>) outerList, innerList, 0, nums);
return outerList;
}
private void helper(ArrayList<List<Integer>> outerList, ArrayList<Integer> innerList, int start, int[] nums) {
if (!outerList.contains(innerList)) outerList.add(new ArrayList<Integer>(innerList));
for (int i=start; i<nums.length; i++) {
innerList.add(nums[i]);
helper(outerList,innerList,i+1,nums);
innerList.remove(innerList.size()-1);
}
}
}
