[LintCode] 18 Subsets II 解题报告

Description
Given a list of numbers that may has duplicate numbers, return all possible subsets

Notice
Each element in a subset must be in non-descending order.
The ordering between two subsets is free.
The solution set must not contain duplicate subsets.


Example
If S = [1,2,2], a solution is:

[
  [2],
  [1],
  [1,2,2],
  [2,2],
  [1,2],
  []
]

Challenge
Can you do it in both recursively and iteratively?


思路
和Subsets这题差不多，都是套模版。不同的是这题里有重复的问题。
首先还是先排序。输入有序的情况下我们更方便判断重复。
举个例子。如果输入是[1, 2¹, 2², 2³]，上标表示第几个相同的。
如果现在取了[1, 2¹, 2², 2³]。这时候2¹是startPos - 1对应的。接下来递归是从startPos开始选下一个数。
那么再选的时候只能选[1, 2¹, 2², 2³]而不能选[1, 2¹, 2², 2³]，不能跳着选。
不能选的这个情况，如果num[i] == num[i - 1]并且i != startPos （必须先从 startPos开始选），那么说明跳着选了，我们不采用，continue掉。


Code

class Solution {
    /**
     * @param nums: A set of numbers.
     * @return: A list of lists. All valid subsets.
     */
    public ArrayList<ArrayList<Integer>> subsetsWithDup(int[] nums) {
        // write your code here
        ArrayList<ArrayList<Integer>> result = new ArrayList<>();
        
        if (nums == null || nums.length == 0) {
            return result;
        }
        
        Arrays.sort(nums);
        
        ArrayList<Integer> subset = new ArrayList<Integer>();
        search(nums, subset, result, 0);
        return result;
    }
    
    public void search( int[] nums,
                        ArrayList<Integer> subset,
                        ArrayList<ArrayList<Integer>> result, 
                        int startPos) {
        
        result.add(new ArrayList(subset));
        
        for (int i = startPos; i < nums.length; i++) {
            if (i - 1 >= startPos && nums[i] == nums[i - 1]) {
                continue;
            }
            subset.add(nums[i]);
            search(nums, subset, result, i + 1);
            subset.remove(subset.size() - 1);
        }
        
        return;
    }
}