Subsets Ⅱ

Despriction

给定一个可能具有重复数字的列表，返回其所有可能的子集

** 注意事项**

• 子集中的每个元素都是非降序的
• 两个子集间的顺序是无关紧要的
• 解集中不能包含重复子集

样例
如果 S =[1,2,2]，一个可能的答案为：

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

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<ArrayList<Integer>>();
            if (nums == null || nums.length == 0) {
                return result;
            }
            Arrays.sort(nums);
            ArrayList<Integer> list = new ArrayList<Integer>();
            subsetsHelp(result, list, nums, 0);

            return result;
        }

    public void subsetsHelp(ArrayList<ArrayList<Integer>> result, ArrayList<Integer> list, int[] nums, int pos) {
        result.add(new ArrayList<Integer>(list));
        for (int i = pos; i < nums.length; i++) {
            if (i != pos && nums[i] == nums[i - 1]) {
                continue;
            }
            list.add(nums[i]);
            subsetsHelp(result, list, nums, i + 1);
            list.remove(list.size() - 1);
        }
    }
}

Subsets Ⅱ