LeetCode題解：Subsets II

LeetCode題解：Subsets II

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],
[]
]

題意：給定數組，可能有重復元素，求其所有可能的自己（Subsets的去重）

解決思路：記錄一下重復數的個數，對其特別處理下就可以

代碼：

public class Solution {
    public List> subsetsWithDup(int[] nums) {
        List> result = new ArrayList>();
        result.add(new ArrayList());
        Arrays.sort(nums);

        for(int i = 0; i < nums.length; i++){
            int dup = 0;

            while((i + 1) < nums.length && nums[i + 1] == nums[i]){
                dup++;
                i++;
            }

            int currSize = result.size();
            for(int j = 0; j < currSize; j++){
                List temp = new ArrayList(result.get(j));

                for(int t = 0; t <= dup; t++){
                    temp.add(nums[i]);
                    result.add(new ArrayList(temp));
                }
            }
        }

        return result;
    }
}