Subsets II(Medium)

Given a collection of integers that might contain duplicates, nums, return all possible subsets.

Note:

1. elements in a subset must be in non-descending order.
2. 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],
  []
]

解题思路

此题在上一题的基础上加了有重复元素的情况，因此需要对回溯函数进行一定的剪枝，对于排列组合的模板程序，剪枝通常可以从两个地方出发，一是在返回结果result.add之前进行剪枝，另一个则是在list.add处剪枝，具体使用哪一种需要视情况而定，哪种简单就选谁。

由于此题所给数组不一定有序，故首先需要排序。有重复元素对最终结果的影响在于重复元素最多只能出现n次(重复个数为n时)。具体分析过程如下(此分析过程改编自 九章算法)。

本题思路类似于Permutations II

public List<List<Integer>> subsets(int[] nums) {
    List<List<Integer>> result = new ArrayList<List<Integer>>();
    List<Integer> list = new ArrayList<Integer>();
    if (nums == null || nums.length == 0) {
        return result;
    }

    Arrays.sort(nums);
    dfs(nums, 0, list, result);

    return result;
}

private void dfs(int[] nums, int pos, List<Integer> list,
                     List<List<Integer>> ret) {

    // add temp result first
    ret.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]);
        dfs(nums, i + 1, list, ret);
        list.remove(list.size() - 1);
    }
}