78&90. 子集&子集 II（回溯法）

本题来自 LeetCode：78. 子集^[1]

78. 子集

题目描述

给定一组不含重复元素的整数数组 nums，返回该数组所有可能的子集（幂集）。
说明：解集不能包含重复的子集。
示例:

输入: nums = [1,2,3]
输出:
[
 [3],
  [1],
  [2],
  [1,2,3],
  [1,3],
  [2,3],
  [1,2],
  []
]

题目分析

先看下子集的相关概念：设全集`I`的元素个数为`n`，它的子集个数为`2^n`，真子集的个数为`(2^n)-1`，非空真子集的个数为`(2^n)-2`；

由于不包含重复元素，因此本题就是求子集的个数；

本题比较简单，可以采用回溯法，对于任一一个元素要么存在于子集中，要么不存在于子集中；

题目解答

解法一

class Solution {
    public ListListInteger subsets(int[] nums) {
        ListListInteger lists = new LinkedList();
        backtracing(lists, new LinkedList(), nums, 0);
        return lists;
    }

    /**
     *
     * @param lists 子集集合
     * @param list  当前子集
     * @param nums  数组
     * @param index 当前处理的数的下标
     */
    public void backtracing(ListListInteger lists,
                            ListInteger list,
                            int[] nums,
                            int index) {
        if (index == nums.length) {
            lists.add(new LinkedList(list));
            return;
        }
        // nums[index]不加入子集的情况
        backtracing(lists, list, nums, index + 1);
        list.add(nums[index]);
        // nums[index]加入子集的情况
        backtracing(lists, list, nums, index + 1);
        list.remove(list.size() - 1);
    }
}

复杂度分析：
时间复杂度： O(2^n)
空间复杂度： O(n)

解法二

class Solution {
    public ListListInteger subsets(int[] nums) {
        ListListInteger lists = new LinkedList();
        backtracing(lists, new LinkedList(), nums, 0);
        return lists;
    }

    /**
     *
     * @param lists 子集集合
     * @param list  当前子集
     * @param nums  数组
     * @param index 当前处理的数的下标
     */
    public void backtracing(ListListInteger lists,
                            ListInteger list,
                            int[] nums,
                            int index) {
        // nums[index]不加入子集的情况
        lists.add(new LinkedList(list));
        // nums[index]加入子集的情况
        for(int i = index; i  nums.length; i ++) {
            list.add(nums[i]);
            backtracing(lists, list, nums, i + 1);
            list.remove(list.size() - 1);
        }
    }
}

复杂度分析：
时间复杂度： O(n!)
空间复杂度： O(n)

90. 子集 II

本题来自 LeetCode：90. 子集 II^[2]

题目详情

给定一个可能包含重复元素的整数数组 nums，返回该数组所有可能的子集（幂集）。
说明：解集不能包含重复的子集。
示例:

输入: [1,2,2]
输出:
[
  [2],
  [1],
  [1,2,2],
  [2,2],
  [1,2],
  []
]

题目分析

本题和 78. 子集最大的不同在于，数组 nums可包含重复元素，但是子集集合中 不能包含重复的子集。
首先来看一下包含重复元素的子集情况，定义数组 [2, 2, 2]，它的 不包含重复的子集的集合，可以直接枚举出来：

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

从上可以发现规律， n个相等的元素 k，其不重复的组合就是其个数的组合，子集分别为 0个k、 1个k、 ...、 n个k。
因此需要对重复的元素单独求子集集合。

题目解答

class Solution {
    public ListListInteger subsetsWithDup(int[] nums) {
        ListListInteger lists = new LinkedList();
        // 数组排序，让重复的元素相邻，便于操作
        Arrays.sort(nums);
        backtracing(lists, new LinkedList(), nums, 0);
        return lists;
    }
    /**
     *
     * @param lists 子集集合
     * @param list  当前子集
     * @param nums  数组
     * @param index 当前处理的数的下标
     */
    public void backtracing(ListListInteger lists,
                            ListInteger list,
                            int[] nums,
                            int index) {
        if (index == nums.length) {
            lists.add(new LinkedList(list));
            return;
        }
        // 找到值等于nums[index]的区间[index, lastIndex]
        int lastIndex = index;
        while(lastIndex + 1  nums.length && nums[index] == nums[lastIndex + 1]) {
            lastIndex ++;
        }
        // nums[index]不加入子集的情况
        backtracing(lists, list, nums, lastIndex + 1);
        // nums[index]在子集中出现的次数在范围[1, lastIndex + 1]时
        for(int i = index; i  lastIndex + 1; i ++) {
            list.add(nums[index]);
            backtracing(lists, list, nums, lastIndex + 1);
        }
        // 将元素nums[index]全部移出
        for(int i = index; i  lastIndex + 1; i++) {
            list.remove(list.size() - 1);
        }
    }
}

以上解法没有用变量 lastIndex=lastIndex + 1 替代 lastIndex + 1，是为了更好地理解边界 nums[lastIndex] = nums[index]，也就是说 nums区间 [index, lastIndex]的值都等于 nums[index]；
值 lastIndex + 1可能等于 nums.length，也可能 nums[lastIndex + 1] nums[index]；

复杂度分析：
时间复杂度： O(2^n)
空间复杂度： O(n)

参考资料

78. 子集: https://leetcode-cn.com/problems/subsets/

79. 子集 II: https://leetcode-cn.com/problems/subsets-ii

原文始发于微信公众号（xiaogan的技术博客）：