Leetcode - 90. 子集 II

class Solution {

    // 和第78题（https://leetcode-cn.com/problems/subsets/）类似，注意结果去重即可
    public List<List<Integer>> subsetsWithDup(int[] nums) {
        List<List<Integer>> ret = new ArrayList<>();

        // 去重操作1：排序
        Arrays.sort(nums);
        
        // 依次找到所有长度为0, 1, 2, ..., nums.length的子集
        for (int i = 0; i <= nums.length; i++) {
            dfs(nums, 0, new int[i], 0, ret);
        }
        
        return ret;
    }

    // 该方法作用：将nums的[begin, length)区间上的元素依次赋值给subset[idx]
    // begin的作用是限制程序只能从左向右遍历nums数组，避免产生重复的子集
    private static void dfs(int[] nums, int begin, int[] subset, int idx, List<List<Integer>> ret){
        
        // 如果数字的个数达到了要求，此时将arr作为一个组合存到ret中
        if (idx == subset.length) {
            List<Integer> list = new ArrayList<>(subset.length);
            for (int i : subset) {
                list.add(i);
            }
            ret.add(list);
            return;
        }

        // 剪枝；如果subset中的空位个数比nums能提供的数字个数还多，则肯定不能找到有效的组合，因此直接返回
        if (subset.length - idx > nums.length - begin) {
            return;
        }

        // 去重操作2：记录上次使用的数字
        int lastUsedNum = nums[0] - 1;

        // 将nums的[begin, length)区间上的元素依次赋值给subset[idx]
        for (int i = begin; i < nums.length; i++) {
            
            // 去重操作3：如果该数字在上次循环中使用已经使用了，则跳过
            if (lastUsedNum == nums[i]) {
                continue;
            }

            // 去重操作4：记录下当前使用过的数字
            lastUsedNum = nums[i];
            
            subset[idx] = nums[i];

            // 继续往下搜索
            dfs(nums, i + 1, subset, idx + 1, ret);
        }
    }
}